我是通过的第二篇学会的
这篇也总结的很好，附带很多经典的习题
这是bin神的总结：
这是kss的板子：
这个板子用了tire图的优化，即不需要失配回溯，，效率大大提高
本题代码：
普通模版：
//826MS 28308K #include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;#define MAXN 500500#define M 1001000char s[55];char desc[M];struct node{node *next[26];node *fail;int cnt;}tire[MAXN],*que[MAXN],*root;struct AC{int L,head,tail;node *createnode(){memset(tire[L].next,0,sizeof(tire[L].next));tire[L].fail=NULL;tire[L].cnt=0;return &tire[L++];}void ini(){L=head=tail=0;root=createnode();}void Insert(char str[]){node *cur=root;for(int i=0;str[i];i++){int val=str[i]-'a';if(!cur->next[val]){cur->next[val]=createnode();}cur=cur->next[val];}cur->cnt++;}void build(){que[head++]=root;while(tail<head){node *cur=que[tail++];for(int i=0;i<26;i++){if(cur->next[i]!=NULL){node *tmp=cur;tmp=tmp->fail;while(tmp!=NULL){if(tmp->next[i]!=NULL){cur->next[i]->fail=tmp->next[i];break;}tmp=tmp->fail;}if(tmp==NULL) cur->next[i]->fail=root;que[head++]=cur->next[i];}}}}int query(char str[]){int ans=0;node *cur=root;for(int i=0;str[i];i++){int val=str[i]-'a';while(cur!=root&&cur->next[val]==NULL) cur=cur->fail;cur= cur->next[val];cur=(cur==NULL) ? root:cur;node *tmp = cur;while(tmp!=root){ans+=tmp->cnt;tmp->cnt=0;tmp=tmp->fail;}}return ans;}}ac;int main(){int T;scanf("%d",&T);while(T–){ac.ini();int m;scanf("%d",&m);while(m–){scanf("%s",s);ac.Insert(s);}ac.build();scanf("%s",desc);printf("%d\n",ac.query(desc));}return 0;}tire图优化模版：（可见效率提高了很多）//249MS 28308K #include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;#define MAXN 500500#define M 1001000char s[55];char desc[M];struct node{node *next[26];node *fail;int cnt;}trie[MAXN],*que[MAXN],*root;struct AC{int head,tail,L;node* createnode(){trie[L].fail=NULL;memset(trie[L].next,0,sizeof(trie[L].next));trie[L].cnt=0;return &trie[L++];}void ini(){head=tail=L=0;root=createnode();}void Insert(char str[]){node *cur=root;for(int i=0;str[i];i++){int val=str[i]-'a';if(cur->next[val]==NULL)cur->next[val]=createnode();cur=cur->next[val];}cur->cnt++;}void build(){que[head++]=root;while(head>tail){node *cur=que[tail++];for(int i=0;i<26;i++){if(cur->next[i]!=NULL){if(cur==root) cur->next[i]->fail=root;else cur->next[i]->fail=cur->fail->next[i];que[head++]=cur->next[i];}else {if(cur==root) cur->next[i]=root;else cur->next[i] = cur->fail->next[i];}}}}int query(char str[]){int ans=0;node *cur=root;for(int i=0;str[i];i++){int val=str[i]-'a';cur=cur->next[val];if(cur->cnt){node *tmp=cur;while(tmp!=root){ans+=tmp->cnt;tmp->cnt=0;tmp=tmp->fail;}}}return ans;}}ac;int main(){int T;scanf("%d",&T);while(T–){ac.ini();int m;scanf("%d",&m);while(m–){scanf("%s",s);ac.Insert(s);}ac.build();scanf("%s",desc);printf("%d\n",ac.query(desc));}return 0;}
什么天荒地老，什么至死不渝。都只是锦上添花的借口…
