/*
hdu 2896 病毒侵袭 ac自动机
从题意得知，模式串中没有重复的串出现，所以结构体中可以将last[]（后缀链接）数组去掉
last[]数组主要是记录具有相同后缀模式串的末尾节点编号 。本题中主要是计算每一个模式串
在主串中有没有出现过，而不是计算出现过多少次，所以将last[]数组省掉....
*/
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define N 210*500
using namespace std;
class AC_atomata
{
public:
int trie[N][128], f[N], val[N];
int vis[510];
int nodeN;
int total;
queue<int>q;
void init()
{
nodeN=0;
val[0]=0;
total=0;
while(!q.empty()) q.pop();
memset(trie[0], 0, sizeof(trie[0]));
}
void build(char *str, int index);//建立trie树
void getFail();//失配函数
void find(char *T, int n, int index);//查找函数
};
void AC_atomata::build(char *str, int index)
{
int i, u;
for(i=0, u=0; str[i]; ++i)
{
int ch=str[i];
if(!trie[u][ch])
{
trie[u][ch]=++nodeN;
memset(trie[nodeN], 0, sizeof(trie[nodeN]));
}
u=trie[u][ch];
val[u]=0;
}
val[u]=index;
}
void AC_atomata::getFail()
{
int r, u, v, i;
f[0]=0;
for(i=0; i<128; ++i)
{
if(trie[0][i])
{
q.push(trie[0][i]);
f[trie[0][i]]=0;
}
}
while(!q.empty())
{
r=q.front();
q.pop();
for(i=0; i<128; ++i)
{
u=trie[r][i];
if(!u) continue;
q.push(u);
v=f[r];
while(v && !trie[v][i]) v=trie[v][i];
f[u]=trie[v][i];
}
}
}
void AC_atomata::find(char *T, int n, int index)
{
int i, u;
int cnt=0, v[3];
memset(v, 0, sizeof(v));
memset(vis, 0, sizeof(vis));//每一次查找将数组初始化，开始忘记初始化了， 哇了好多次
for(i=0, u=0; T[i]; ++i)
{
int ch=T[i];
while(u && !trie[u][ch]) u=f[u];
u=trie[u][ch];
if(val[u] && !vis[val[u]])
{
v[cnt++]=val[u];
vis[val[u]]=1;
if(cnt>2) break;
}
}
if(cnt>0)
{
++total;
printf("web %d:", index);
sort(v, v+3);
for(i=0; i<3; ++i)
if(v[i]) printf(" %d", v[i]);
printf("\n");
}
}
AC_atomata ac;
char T[10005], s[205];
int main()
{
int n, m, i;
while(scanf("%d", &n)!=EOF)
{
ac.init();
for(i=1; i<=n; ++i)
{
scanf("%s", s);
ac.build(s, i);
}
ac.getFail();
scanf("%d", &m);
for(i=1; i<=m; ++i)
{
scanf("%s", T);
ac.find(T, n, i);
}
printf("total: %d\n", ac.total);
}
return 0;
}
/*
上面的程序过了，感觉数据很水....
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define N 100005
#define M 505
using namespace std;
int n, m;
class AC_atomata
{
public:
int trie[N][128], fail[N];
int cnt;
int vis[M];//标记边
int nodeN;//节点数
int val[N];//标记字符节点是否为单词末尾
queue<int>q;
void init();
void build(char *T, int index) ;
void getFail();
void find(char *S, int index);
};
void AC_atomata:: init()
{
while(!q.empty()) q.pop();
memset(trie[0], 0, sizeof(trie[0]));
nodeN=0;
cnt=0;
memset(val, 0, sizeof(val));
}
void AC_atomata:: build(char *T, int index)
{
int i, u=0;
for(i=0; T[i]; ++i)
{
if(trie[u][T[i]]==0)
{
trie[u][T[i]]=++nodeN;
memset(trie[nodeN], 0, sizeof(trie[nodeN]));
}
val[u]=0;
u=trie[u][T[i]];
}
val[u]=index;
}
void AC_atomata:: getFail()
{
int r, u, v;
int c, root=0;
fail[root]=0;
for(c=0; c<128; ++c)
{
if(v=trie[root][c])
{
fail[v]=root;
q.push(v);
}
}
while(!q.empty())
{
r=q.front(); q.pop();
for(c=0; c<128; ++c)
{
u=trie[r][c];
if(!u)//该节点不存在，也就是查找过程中每一个节点都是平等的
trie[r][c]=trie[fail[r]][c];
else
{
fail[u]=trie[fail[r]][c];
q.push(u);
}
}
}
}
void AC_atomata:: find(char *S, int index)
{
int cur, root, count=0;
cur=root=0;
memset(vis, 0, sizeof(vis));
for(int i=0; S[i]; ++i)
{
cur=trie[cur][S[i]];
int next=cur;
//这个while循环就是last[]数组实现的功能，只不过是last[]数组记录的总是单词结尾字符的节点的编号
//而我们通过沿着 next 节点的失配方向一直搜索， 也可以寻找到 以next节点所对应字符结尾的单词
while(next!=root)
{
if(val[next])
{
vis[val[next]]=1;
count++;
}
next=fail[next];
}
}
if(count>0)
{
++cnt;
printf("web %d:", index);
for(int i=1; i<=n; ++i)
if(vis[i])
printf(" %d", i);
printf("\n");
}
}
char t[205], s[10005];
AC_atomata ac;
int main()
{
int i;
while(scanf("%d", &n)!=EOF)
{
ac.init();
for(i=1; i<=n; ++i)
{
scanf("%s", t);
ac.build(t, i);
}
ac.getFail();
scanf("%d", &m) ;
for(i=1; i<=m; ++i)
{
scanf("%s", s);
ac.find(s, i);
}
printf("total: %d\n", ac.cnt);
}
return 0;
}
本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3801731.html，如需转载请自行联系原作者
