算是AC自動機裡面的裸題吧 可惡的re了幾次 看清題目 沒說是由小寫字母構成 , 所以next得開到127 考慮到所有的字符才行, 注意不能算重復那裡我用了一個變量flash來標記每次查找是否走過 如果flash=當前編號的網站 則是走過,,其它也沒啥了
#include#include #include #include #include #include using namespace std; struct node { node *fail; node *next[127]; int flash; int cont; int id; }*a,*b,*root; char word[20010]; int num[1010],print[1100][1010]; int keytree(char str[],int k) { int len=strlen(str); node *p,*q; p=root; for(int i=0;i<len;i++) { if(p->next[str[i]-32]!=NULL) p=p->next[str[i]-32]; else { q=(struct node*)malloc(sizeof(struct node)); memset(q,NULL,sizeof(struct node)); p->next[str[i]-32]=q; p=q; } } p->cont++; p->id=k; return 0; } int make_fail() { queue<node*>Q; root->fail=NULL; a=root; Q.push(a); while(!Q.empty()) { b=Q.front(); Q.pop(); for(int i=0;i<127;i++) { if(b->next[i]!=NULL) { if(b==root) { b->next[i]->fail=root; } else { a=b->fail; while(a!=NULL) { if(a->next[i]!=NULL) { b->next[i]->fail=a->next[i]; break; } a=a->fail; } if(a==NULL) b->next[i]->fail=root; } Q.push(b->next[i]); } } } return 0; } int find(char str[],int k) { int len=strlen(str); int sum=0; struct node *p,*q; p=root; for(int i=0;i<len;i++) { while(p->next[str[i]-32]==NULL&&p!=root) p=p->fail; p=p->next[str[i]-32]; if(p==NULL) p=root; q=p; while(q->flash!=k&&q!=root) { if(q->cont) { sum++; num[sum]=q->id; } q->flash=k; q=q->fail; } } return sum; } int main() { int n,i,j; char str[500]; scanf("%d",&n); getchar(); root=(struct node*)malloc(sizeof(struct node)); memset(root,NULL,sizeof(struct node)); for(i=1;i<=n;i++) { gets(str); keytree(str,i); } make_fail(); int m; int x=0; int t; int number[1100]; scanf("%d",&m); getchar(); for(i=1;i<=m;i++) { gets(word); t=find(word,i); if(t) { sort(num+1,num+1+t); x++; number[x]=i; print[x][0]=t; for(j=1;j<=t;j++) print[x][j]=num[j]; } } for(i=1;i<=x;i++) { printf("web %d:",number[i]); for(j=1;j<=print[i][0];j++) printf(" %d",print[i][j]); printf("\n"); } printf("total: %d\n",x); return 0; }