初学ac自动机。还要努力。参考了许多代码，仿佛是拷贝的一样了。。。。
// hdu Aho-Corasick automation.cpp : 定义控制台应用程序的入口点。 // #include <iostream> #include <algorithm> #include <queue> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> using namespace std; int n; char str[1100000]; int ans; struct node { int f; node *fail,*next[26]; node() { f=false; fail=NULL; memset(next,NULL,sizeof(next)); } }*root; void ini() { char s[55]; cin>>n; ans=0; root=new node; root->fail=NULL; root->f=false; memset(root->next,NULL,sizeof(root->next)); for(int i=1;i<=n;i++) { scanf("%s",s); node *tmp=root; for(int j=0;s[j]!=' ';j++) { if(tmp->next[s[j]-'a']==NULL) { tmp->next[s[j]-'a']=new node; } tmp=tmp->next[s[j]-'a']; } tmp->f++; } scanf("%s",str); } void del(node *r) { if(r==NULL) return; for(int i=0;i<26;i++) { if(r->next[i]!=NULL) { del(r->next[i]); } delete r->next[i]; } } void getfail() { queue<node*> mq; root->fail=NULL; mq.push(root); while(!mq.empty()) { node *tmp=mq.front(),*lfail; mq.pop(); for(int i=0;i<26;i++) { lfail=tmp->fail; if(tmp->next[i]) { while(lfail) { if(lfail->next[i]) { tmp->next[i]->fail=lfail->next[i]; break; } lfail=lfail->fail; } if(lfail==NULL) tmp->next[i]->fail=root; mq.push(tmp->next[i]); } } } } void query() { ans=0; node *p=root; for(int i=0;str[i]!=' ';i++) { int k=str[i]-'a'; while( p->next[k]==NULL && p!=root) p = p->fail; //找下一个位置匹配的指针 p = p->next[k] == NULL?root:p->next[k]; //已经找到或者p=root node *tmp = p; while( tmp != root && tmp->f != -1) //找到所有子匹配求和 { ans += tmp->f; tmp->f = -1; tmp = tmp->fail; } } } int main() { int t; cin>>t; while(t--) { ini(); getfail(); query(); del(root); cout<<ans<<endl; } //scanf("%s",str); return 0; }