差点忘了写。一开始RE，因为和之前一样id=str[i]-‘a’. 这里不用减。。。 然后开始Mle，把数组模拟队列改为了队列，然后c++提交
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #include <cmath> #include <queue> using namespace std; char s[205]; const int n = 128; const int maxn =10010; char s1[maxn]; struct Trie { Trie *fail; Trie *next[n]; int count1; int v; Trie() { v=0; fail=NULL; count1=0; for(int i=0;i<n;i++) next[i]=NULL; } }; Trie *root; int a[5]; void buildTrie(char *s,int num) { int len=strlen(s); len--; Trie *p=root; for(int i=0;i<len;i++) { int id=s[i]; if(p->next[id]==NULL) p->next[id]=new Trie(); p=p->next[id]; } 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; } if(temp->next[i]==NULL) temp=temp->fail; } if(temp==NULL) p->next[i]->fail=root; } q.push(p->next[i]); } } } } int query(char *str,int num) { memset(a,0,sizeof(a)); int len=strlen(str); len--; Trie *p=root; int now=0; for(int i=0;i<len;i++) { int id=str[i]; while(p->next[id]==NULL&&p!=root) p=p->fail; p=p->next[id]; if(p==NULL) p=root; Trie *temp=p; while(temp!=root) { if(now>=3) break; if(temp->count1!=0&&temp->v!=num){ a[now++]=temp->count1; temp->v=num; } else break; temp=temp->fail; } if(now>=3) break; } if(now>0) { sort(a,a+now); printf("web %d:",num); for(int i=0;i<now;i++) printf(" %d",a[i]); printf("\n"); return 1; } else return 0; } int main() { int num; scanf("%d",&num); root=new Trie(); getchar(); for(int i=1;i<=num;i++) { fgets(s,205,stdin); buildTrie(s,i); } buildfail(); int m; scanf("%d",&m); int total=0; getchar(); for(int i=1;i<=m;i++) { fgets(s1,maxn,stdin); if(query(s1,i)) total ++; } printf("total: %d\n",total); return 0; }