查找多个串是否在目标串中出现,简单的AC自动机应用。。。
代码:
#include <iostream>
using namespace std;
struct Node{
int next[100];
int fail, flag;
void init(){
for( int i= 0; i< 100; ++i ) next[i]= 0;
fail= -1; flag= 0;
}
};
Node tb[100000];
int n, cnt, m;
char str[10010];
int mark[1010];
void insert( char*s, int d ){
int rt= 0;
while( *s ){
int t= *s- 30;
if( tb[rt].next[t]== 0 ){
tb[++cnt].init();
tb[rt].next[t]= cnt;
}
rt= tb[rt].next[t]; s++;
}
tb[rt].flag= d;
}
int que[100000], head, tail;
void build(){
int q, p;
head= 0, tail= 0, que[0]= 0;
while( head<= tail ){
int now= que[head++];
for( int t= 0; t< 100; ++t )
if( tb[now].next[t] ){
p= tb[now].next[t]; q= tb[now].fail;
while( q!= -1 && !tb[q].next[t] ) q= tb[q].fail;
if( q== -1 ) tb[p].fail= 0;
else tb[p].fail= tb[q].next[t];
que[++tail]= p;
}
}
}
void match( char*s ){
int rt= 0, q, p;
while( *s ){
int t= *s- 30;
if( tb[rt].next[t] ) rt= tb[rt].next[t];
else{
p= tb[rt].fail;
while( p!= -1 && !tb[p].next[t] ) p= tb[p].fail;
if( p== -1 ) rt= 0;
else rt= tb[p].next[t];
}
if( tb[rt].flag ){
mark[ tb[rt].flag ]= 1;
p= tb[rt].fail;
while( p && !mark[ tb[p].flag ] ){
mark[ tb[p].flag ]= 1;
p= tb[p].fail;
}
}
s++;
}
}
int main(){
cnt= 0; tb[0].init();
scanf("%d",&n );
for( int i= 1; i<= n; ++i ){
scanf("%s",str );
insert( str, i );
}
build();
scanf("%d",&m );
int ans= 0;
for( int i= 1; i<= m; ++i ){
for( int j= 0; j<= n; ++j ) mark[j]= 0;
scanf("%s", str );
match( str );
int num= 0;
for( int j= 1; j<= n; ++j ) num+= mark[j];
if( num ){
ans++;
printf("web %d:", i );
for( int j= 1; j<= n; ++j )
if( mark[j] ) printf(" %d", j );
puts("");
}
}
printf("total: %d\n", ans );
return 0;
}
分享到:
相关推荐
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
hdu2000-2014ac代码,虽然只有几道,但都是简单的
hdu 一些简单题目 ac代码 大概100道
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了
HDU最全ac代码
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
收集的部分HDOJ杭电ACM题的代码 大牛勿下 全是基础供初级acmer使用
hdu杭电所有题目按照ac数量排序,python分析
hdu2101AC代码
自己做的HDU ACM已经AC的题目
一款 HDU OJ 的自动刷题工具,搜索来源可选用 百度搜索 / 必应搜索,支持并行以及串行查找,祝早日刷上航电首页哦~ 使用 Python 编写,执行之前你需要在同目录下创建文件 aclog.txt ,然后粘贴进你目前已经 AC 的...
ACM hdu 代码大全3000例,hdu已经AC的3000例代码,部分代码有详细解析
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
这是我自己的AC代码,都是自己做的,有的很容易出错,大家看的时候要仔细点,加油
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门