网址：https://vjudge.net/problem/HDU-2222
题意：
统计模式串在文本串的出现次数，文本串只含有小写字母。
题解：
$AC$自动机的模板题，在$Trie$树上建出$Trie$图，然后查询的时候跳$fail$指针直到已访问结点或者根结点记录数量，标记已访问结点即可。
AC代码：
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
#define maxn int(5e5+9)
#define m(a,b) memset (a,b,sizeof(a));
#pragma GCC Optimize(2)
int trie[maxn][26];
int cntword[maxn];
int fail[maxn];
int cnt = 0,ans=0;
struct AC
{
void insert(char *str)
{
int root = 0, next;
int len=strlen(str);
for (int i = 0; i < len; ++i)
{
next = str[i] - 'a';
if (!trie[root][next])
trie[root][next] = ++cnt;
root = trie[root][next];
}
++cntword[root];
}
void buildfail()
{
queue<int>que;
for (int i = 0; i < 26; ++i)
if (trie[0][i])
{
que.push(trie[0][i]);
fail[trie[0][i]] = 0;
}
while (!que.empty())
{
int now = que.front();
que.pop();
for (int i = 0; i < 26; ++i)
{
if (trie[now][i])
{
fail[trie[now][i]] = trie[fail[now]][i];
que.push(trie[now][i]);
}
else
trie[now][i] = trie[fail[now]][i];
}
}
}
void query(char *str)
{
int now = 0;
int len=strlen(str);
for (int i = 0; i < len; ++i)
{
now = trie[now][str[i] - 'a'];
for (int j = now; j&&cntword[j]!=-1 ; j = fail[j])
{
ans+=cntword[j];
cntword[j]=-1;
}
}
}
};
char mod[55],word[1000005];
int main()
{
int n,m;
AC ac;
scanf("%d",&n);
while(n--)
{
m(trie,0);
m(fail,0);
m(cntword,0);
ans=0;
scanf("%d",&m);
for(int i=0;i<m;++i)
{
scanf("%s",mod);
ac.insert(mod);
}
ac.buildfail();
scanf("%s",word);
ac.query(word);
printf("%d\n",ans);
}
return 0;
}