大概就是裸的AC自动机了
#include<stdio.h> #include<algorithm> #include<string.h> #include<queue> using namespace std; #define MAXN 130 class node { public: node *fail; node *next[MAXN]; int ind; node () { fail=0; ind=0; memset(next,0,sizeof(next)); } }; char s1[1010][55]; char s2[2000010]; int cnt[1010]; node *root; void Insert(char *s,int id) { node *p=root; while(*s) { int ind=*s-' '; if(p->next[ind]==NULL) p->next[ind]=new node; p=p->next[ind]; s++; } p->ind=id; } queue<node *>q1; void Build() { q1.push(root); root->fail=NULL; while(!q1.empty()) { node *p=NULL; node *now=q1.front(); q1.pop(); for(int i=0;i<MAXN;i++) { if(now->next[i]) { if(now==root) now->next[i]->fail=root; else { p=now->fail; while(p) { if(p->next[i]) { now->next[i]->fail=p->next[i]; break; } p=p->fail; } if(p==NULL) now->next[i]->fail=root; } q1.push(now->next[i]); } } } } void dfs(node *p) { for(int i=0;i<MAXN;i++) if(p->next[i]) dfs(p->next[i]); delete p; } int main() { int n; while(scanf("%d",&n)!=EOF) { root=new node; memset(cnt,0,sizeof(cnt)); for(int i=1;i<=n;i++) { scanf("%s",s1[i]); Insert(s1[i],i); } Build(); scanf("%s",s2); int len=strlen(s2); node *p=root; for(int i=0;i<len;i++) { int ind=s2[i]-' '; while(p->next[ind]==NULL&&p!=root) p=p->fail; p=p->next[ind]; if(!p) p=root; node *now=p; while(now!=root) { if(now->ind) { cnt[now->ind]++; } now=now->fail; } } for(int i=1;i<=n;i++) { if(cnt[i]) printf("%s: %d ",s1[i],cnt[i]); } dfs(root); } return 0; }