多组数据呀呀呀。然后我们只用去掉那个count1=-1就好了
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #include <cmath> #include <queue> using namespace std; const int n = 26; int vis[3000]; struct Trie { Trie *next[n]; Trie *fail; int count1; int v; Trie() { fail=NULL; for(int i=0;i<n;i++) next[i]=NULL; count1=0; v=0; } }; Trie *root; void buildTrie(char *str,int num) { int len=strlen(str); Trie *p=root; for(int i=0;i<len;i++) { int id=str[i]-'A'; if(p->next[id]==NULL) p->next[id]=new Trie(); p=p->next[id]; p->v=num; } p->count1=num; } void buildfail() { queue <Trie* > q; q.push(root); while(!q.empty()) { Trie *p=q.front();q.pop(); for(int i=0;i<n;i++) { if(p->next[i]!=NULL) { if(p==root) p->next[i]->fail=root; else { Trie *temp=p->fail; while(temp!=NULL) { if(temp->next[i]!=NULL) { p->next[i]->fail=temp->next[i]; break; } temp=temp->fail; } if(temp==NULL) p->next[i]->fail=root; } q.push(p->next[i]); } } } } void qurey(char *str) { int len=strlen(str); Trie *p=root; len--; for(int i=0;i<len;i++) { if(str[i]>='A'&&str[i]<='Z') { int id=str[i]-'A'; while(p->next[id]==NULL&&p!=root) p=p->fail; p=p->next[id]; if(p==NULL) p=root; Trie *temp=p; int flag=0; int k=temp->v; while(temp!=root) { vis[temp->count1]++; temp=temp->fail; } } else p=root; } } char s[1005][100]; char str[2000010]; int main() { int n; while(scanf("%d",&n)!=EOF){ root=new Trie(); for(int i=1;i<=n;i++) { scanf("%s",s[i]); buildTrie(s[i],i); } buildfail(); getchar(); fgets(str,2000010,stdin); memset(vis,0,sizeof(vis)); qurey(str); for(int i=1;i<=n;i++) { if(vis[i]>0) printf("%s: %d\n",s[i],vis[i]); } } return 0; }