HDU 3065，模板（备忘录）
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
using namespace std;
#define M 2222222
char sx[][];
int n;
char s[M]; struct Trie{
int ch[M][],end[M],fail[M],cnt,root;
int b[M];
int Newnode(){
cnt++;
memset(ch[cnt],-,sizeof(ch[cnt]));
end[cnt]=-;
fail[cnt]=-;
return cnt;
}
void init(){
cnt=;
root=Newnode();
memset(b,,sizeof(b));
} void insert(char *s,int x){
int len=strlen(s),pos=root;
for (int i=;i<len;i++){
int v=s[i];
if (ch[pos][v]==-) ch[pos][v]=Newnode();
pos=ch[pos][v];
}
end[pos]=x;
} queue<int> Q;
void get_fail()
{
fail[root]=root;
for (int i=;i<;i++){
if (ch[root][i]==-) ch[root][i]=root;
else {
fail[ch[root][i]]=root;
Q.push(ch[root][i]);
}
}
while (!Q.empty()){
int pos=Q.front();
Q.pop();
for (int i=;i<;i++)
if (ch[pos][i]==-) ch[pos][i]=ch[fail[pos]][i];
else {
fail[ch[pos][i]]=ch[fail[pos]][i];
Q.push(ch[pos][i]);
}
}
}
void query(char *s1){
int len=strlen(s1),pos=root;
for (int i=;i<len;i++){
if (s1[i]<'A'||s1[i]>'Z') {pos=root;continue;}
int temp=ch[pos][s1[i]];
pos=temp;
while (temp!=root){
if (end[temp]!=-) b[end[temp]]++;
temp=fail[temp];
}
}
for (int i=;i<=n;i++)
if (b[i]) printf("%s: %d\n",sx[i],b[i]);
}
}AC; int main(){
while (scanf("%d",&n)!=EOF)
{
AC.init();
for (int i=;i<=n;i++) {
scanf("%s",sx[i]);
AC.insert(sx[i],i);
}
AC.get_fail();
scanf("%s",s);
AC.query(s);
}
return ;
}