HDU2896 AC自动机多串匹配多串

这算是很经典的多模式串多原串的题目了，匹配的复杂度是O(n)的，这样，直接上自动机，注意判重另外开一个vis变量表示第turn躺是否访问过此结点即可。

运用静态分配内存，跑了156ms。

我的代码：

#include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> using namespace std; const int MAX=101100; const int MAXK=128; struct Node{ Node* ne[MAXK]; Node* fail; int cnt,vis; }node[MAX],*root; Node* que[MAX]; char s[11000]; int K,ans[5],top; Node* New(){ Node* ret=&node[K++]; ret->fail=NULL; ret->cnt=0; ret->vis=0; for(int i=0;i<MAXK;i++){ ret->ne[i]=NULL; } return ret; } void init(){ K=0; root=New(); } void insert(char* s,int num){ Node* ptr=root; char* p=s; int id; while(*p){ id=*(p++); if(ptr->ne[id]==NULL){ ptr->ne[id]=New(); } ptr=ptr->ne[id]; } ptr->cnt=num; } void bfs(){ int b=0,f=0; Node* now; Node* ptr; que[b++]=root; while(f!=b){ now=que[f++]; for(int i=0;i<MAXK;i++){ if(now->ne[i]!=NULL){ if(now==root){ now->ne[i]->fail=root; }else{ ptr=now->fail; while(ptr!=NULL){ if(ptr->ne[i]!=NULL){ now->ne[i]->fail=ptr->ne[i]; break; }else{ ptr=ptr->fail; } } if(ptr==NULL){ now->ne[i]->fail=root; } } que[b++]=now->ne[i]; } } } } void find(char* s,int turn){ bool vis[520]={0}; Node* ptr=root; Node* next; char* p=s; int id; vis[0]=true; top=0; while(*p){ id=*(p++); while(ptr->ne[id]==NULL&&ptr!=root){ ptr=ptr->fail; } ptr=ptr->ne[id]; if(ptr==NULL){ ptr=root; } next=ptr; while(next!=NULL&&next->vis!=turn){ if(!vis[next->cnt]){ ans[top++]=next->cnt; vis[next->cnt]=true; } next->vis=turn; next=next->fail; } } } int main(){ int n,tol; while(~scanf("%d",&n)){ init(); gets(s); for(int i=1;i<=n;i++){ gets(s); insert(s,i); } bfs(); scanf("%d",&n); tol=0; gets(s); for(int i=1;i<=n;i++){ gets(s); find(s,i); if(top){ printf("web %d:",i); sort(ans,ans+top); for(int j=0;j<top;j++){ printf(" %d",ans[j]); } puts(""); tol++; } } printf("total: %d/n",tol); } return 0; }