/*
啥也不说了，直接套模板。。。
*/
#include<iostream>
#include<map>
#include<string>
#include<cstring>
#include<queue>
#define N 500000
using namespace std;
class AC_Atomata
{
public:
int nodeN;//trie树的节点个数
int trie[N][26];//trie树
int f[N];//失配函数
//map<string, int>ms;//字符串到字符串编号的映射，防止出现多个字符串的模板
int last[N];// last[j]表示节点j沿着失配指针往回走时遇到的下一个单词节点的编号
int cnt;//最多在主串中出现的单词数
int val[N];//标记该节点是否为字符串的端点，该题中val[j]表示以节点j所对应的字符所结束的相同字符串的个数
int vis[N];//标记该节点已经访问过了
queue<int>q;
void init();
void buildTrie(char *p);
void getFail();
void find(char *T);
void countWords(int k);
};
void AC_Atomata::init()
{
nodeN=0;
ms.clear();
memset(vis, 0, sizeof(vis));
memset(trie[0], 0, sizeof(trie[0]));
//memset(cnt, 0, sizeof(cnt));
cnt=0;
}
void AC_Atomata::buildTrie(char *p)
{
int i, u=0;
for(i=0; p[i]; ++i)
{
int k=p[i]-'a';
if(!trie[u][k])
{
memset(trie[nodeN+1], 0, sizeof(trie[nodeN+1])) ;
trie[u][k]=++nodeN;
val[nodeN]=0;
}
u=trie[u][k];
}
++val[u];
//ms[string(p)]=v;
}
void AC_Atomata::getFail()
{
int u, v, r, c;
while(!q.empty()) q.pop();
f[0]=0;
for(c=0; c<26; ++c)
{
u=trie[0][c];
if(u)
{
f[u]=0;
q.push(u);
last[u]=0;
}
}
while(!q.empty())
{
r=q.front();
q.pop();
for(c=0; c<26; ++c)
{
u=trie[r][c];
if(!u) continue;
q.push(u);
v=f[r];
while(v && !trie[v][c]) v=f[v];
f[u]=trie[v][c];
last[u]=val[f[u]] ? f[u] : last[f[u]];
}
}
}
void AC_Atomata::countWords(int k)
{
if(k && !vis[k])
{
//++cnt[val[k]];//k就是该单词所对应的最后一个字符的节点编号，val[k]是这个单词再输入时候的编号
vis[k]=1;//表示以该节点结束的字符串已经访问过了，如果主串中再出现该字符串则不会再计算在内
cnt+=val[k];//
countWords(last[k]);
}
}
void AC_Atomata::find(char *T)
{
int i, j;
for(i=0, j=0; T[i]; ++i)
{
int c=T[i]-'a';
while(j && !trie[j][c]) j=f[j];//一直找到可以匹配的字符节点
j=trie[j][c];
if(val[j])//单词的最后一个字符
countWords(j);
else if(last[j])//如果不是某个单词的最后一个节点
countWords(last[j]);
}
}
AC_Atomata ac;
char T[1000005];
char s[55];
int main()
{
int t, n, i;
scanf("%d", &t);
while(t--)
{
ac.init();
scanf("%d", &n);
for(i=1; i<=n; ++i)
{
scanf("%s", s);
ac.buildTrie(s);
}
scanf("%s", T);
ac.getFail();
ac.find(T);
printf("%d\n", ac.cnt);
}
return 0;
}
/*
咱再换一种方式来写，赶脚这种方式更靠谱一些！
*/
#include<queue>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#define N 500000
using namespace std;
class TRIE
{
public:
int ch[26];//建立trie树的孩子节点个数
int val;//标记该节点是否是单词的结束节点
int fail;//该节点失配时要移向的节点的编号
int last;//后缀连接，示节该点沿着失配指针往回走时遇到的下一个单词节点的编号
int vis;//标记以该点字符所结束的字符串是否已经访问过了
};
class AC_Atomata
{
public:
TRIE trie[N];//建立节点
int nodeN;//trie树的节点的个数
int cnt;//记录节点单词在主串出现的次数
AC_Atomata()
{
nodeN=0;
cnt=0;
trie[0].val=trie[0].vis=0;
memset(trie[0].ch, 0, sizeof(trie[0].ch));
while(!q.empty()) q.pop();
}
queue<int>q;
void buildTrie(char *p);
void getFail();
void find(char *T);
void countWords(int k);
};
void AC_Atomata::buildTrie(char *p)
{
int i, u;
for(i=0, u=0; p[i]; ++i)
{
int k=p[i]-'a';
if(!trie[u].ch[k])
{
trie[u].ch[k]=++nodeN;
memset(trie[nodeN].ch, 0, sizeof(trie[nodeN].ch));
trie[nodeN].val=trie[nodeN].vis=0;
}
u=trie[u].ch[k];
}
++trie[u].val;
}
void AC_Atomata::getFail()
{
int r, u, v, c;
trie[0].fail=0;
for(c=0; c<26; ++c)
{
u=trie[0].ch[c];
if(u)
{
q.push(u);
trie[u].fail=0;
trie[u].last=0;
}
}
while(!q.empty())
{
r=q.front();
q.pop();
for(c=0; c<26; ++c)
{
u=trie[r].ch[c];
if(!u) continue;
q.push(u);
v=trie[r].fail;
while(v && !trie[v].ch[c]) v=trie[v].fail;
v=trie[v].ch[c];//v 节点就是在沿着失配指针往回走时遇到的下一个单词某个字符节点的编号
trie[u].fail=v;
trie[u].last=trie[v].val ? v : trie[v].last;//last记录的总是一个完整的单词最后一个字符节点的编号
}
}
}
void AC_Atomata:: find(char *T)
{
int i, j;
for(i=0, j=0; T[i]; ++i)
{
int k=T[i]-'a';
while(j && !trie[j].ch[k]) j=trie[j].fail;
j=trie[j].ch[k];
if(trie[j].val)
countWords(j);
else if(trie[j].last)
countWords(trie[j].last);
}
}
void AC_Atomata::countWords(int n)
{
if(n && !trie[n].vis)
{
trie[n].vis=1;
cnt+=trie[n].val;
countWords(trie[n].last);
}
}
AC_Atomata ac;
char T[100000];
char s[55];
int main()
{
int t, n;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
for(int i=1; i<=n; ++i)
{
scanf("%s", s);
ac.buildTrie(s);
}
scanf("%s", T);
ac.getFail();
ac.find(T);
printf("%d\n", ac.cnt);
}
return 0;
}
本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3791991.html，如需转载请自行联系原作者
