题意：给出若干个单词和一段文本，问有多少个单词出现在其中。如果两个单词是相同的，得算两个单词的贡献。
分析：直接就是AC自动机的模板了。
具体见代码：
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;
const int MAX_N = + ;
const int MAX_Tot = + ; struct Aho
{
struct state
{
int nxt[];
int fail,cnt;
}stateTable[MAX_Tot]; int size; queue<int> que; void init()
{
while(que.size()) que.pop();
for(int i=;i<MAX_Tot;i++)
{
memset(stateTable[i].nxt,,sizeof(stateTable[i].nxt));
stateTable[i].fail = stateTable[i].cnt = ;
}
size = ;
} void insert(char *s)
{
int n = strlen(s);
int now = ;
for(int i=;i<n;i++)
{
char c = s[i];
if(!stateTable[now].nxt[c-'a'])
stateTable[now].nxt[c-'a'] = size++;
now = stateTable[now].nxt[c-'a'];
}
stateTable[now].cnt++;
} void build()
{
stateTable[].fail = -;
que.push(); while(que.size())
{
int u = que.front();que.pop();
for(int i=;i<;i++)
{
if(stateTable[u].nxt[i])
{
if(u == ) stateTable[stateTable[u].nxt[i]].fail = ;
else
{
int v = stateTable[u].fail;
while(v != -)
{
if(stateTable[v].nxt[i])
{
stateTable[stateTable[u].nxt[i]].fail = stateTable[v].nxt[i];
break;
}
v = stateTable[v].fail;
}
if(v == -) stateTable[stateTable[u].nxt[i]].fail = ;
}
que.push(stateTable[u].nxt[i]);
}
}
}
} int Get(int u)
{
int res = ;
while(u)
{
res += stateTable[u].cnt;
stateTable[u].cnt = ; //这里可做拓展
/*
这里清空的原因如下：
例如单词是he，需要匹配的文本是hehe
那么，我们在匹配完第一个he以后，会再次匹配he，
如果不清空，那么he这个单词就又被匹配了一遍。
10
1
abcab
abcabcab
对上面这个数据，如果不注释掉上面的语句，答案是1.
否则，答案是2.
10
2
abcab
abcabcab
abcabcabcab
*/
u = stateTable[u].fail;
}
return res;
} int match(char *s)
{
int n = strlen(s);
int res = , now = ;
for(int i=;i<n;i++)
{
char c = s[i];
if(stateTable[now].nxt[c-'a']) now = stateTable[now].nxt[c-'a'];
else
{
int p = stateTable[now].fail;
while(p != - && stateTable[p].nxt[c-'a'] == ) p = stateTable[p].fail;
if(p == -) now = ;
else now = stateTable[p].nxt[c-'a'];
}
if(stateTable[now].cnt) res += Get(now);
}
return res;
}
}aho; int T,n;
char s[MAX_N]; int main()
{
int T;scanf("%d",&T);
while(T--)
{
aho.init();
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%s",s);
aho.insert(s);
}
aho.build();
scanf("%s",s);
printf("%d\n",aho.match(s));
}
}
顺便注意上面注释中的拓展点。
————————————————————————————————————————————————
发现上面的代码有问题（虽然能AC），正确代码如下：
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;
const int MAX_N = + ;
const int MAX_Tot = + ; struct Aho
{
struct state
{
int nxt[];
int fail,cnt;
}stateTable[MAX_Tot]; int size; queue<int> que; void init()
{
while(que.size()) que.pop();
for(int i=;i<MAX_Tot;i++)
{
memset(stateTable[i].nxt,,sizeof(stateTable[i].nxt));
stateTable[i].fail = stateTable[i].cnt = ;
}
size = ;
} void insert(char *s)
{
int n = strlen(s);
int now = ;
for(int i=;i<n;i++)
{
char c = s[i];
if(!stateTable[now].nxt[c-'a'])
stateTable[now].nxt[c-'a'] = size++;
now = stateTable[now].nxt[c-'a'];
}
stateTable[now].cnt++;
} void build()
{
stateTable[].fail = -;
que.push(); while(que.size())
{
int u = que.front();que.pop();
for(int i=;i<;i++)
{
if(stateTable[u].nxt[i])
{
if(u == ) stateTable[stateTable[u].nxt[i]].fail = ;
else
{
int v = stateTable[u].fail;
while(v != -)
{
if(stateTable[v].nxt[i])
{
stateTable[stateTable[u].nxt[i]].fail = stateTable[v].nxt[i];
break;
}
v = stateTable[v].fail;
}
if(v == -) stateTable[stateTable[u].nxt[i]].fail = ;
}
que.push(stateTable[u].nxt[i]);
}
}
}
} int Get(int u)
{
int res = ;
while(u)
{
if(stateTable[u].cnt == -) break;
res += stateTable[u].cnt;
stateTable[u].cnt = -;
u = stateTable[u].fail;
}
return res;
} int match(char *s)
{
int n = strlen(s);
int res = , now = ;
for(int i=;i<n;i++)
{
char c = s[i];
if(stateTable[now].nxt[c-'a']) now = stateTable[now].nxt[c-'a'];
else
{
int p = stateTable[now].fail;
while(p != - && stateTable[p].nxt[c-'a'] == ) p = stateTable[p].fail;
if(p == -) now = ;
else now = stateTable[p].nxt[c-'a'];
}
//if(stateTable[now].cnt)
res += Get(now);
}
return res;
}
}aho; int T,n;
char s[MAX_N]; int main()
{
int T;scanf("%d",&T);
while(T--)
{
aho.init();
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%s",s);
aho.insert(s);
}
aho.build();
scanf("%s",s);
printf("%d\n",aho.match(s));
}
}