1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 using namespace std;10 #define Maxn 21011 #define Maxm 100001012 13 struct node14 {15 int son[30],fail,cnt;16 }t[Maxm];int tot;17 18 char s[Maxm];19 int l,bj[Maxn];20 21 void upd(int x)22 {23 memset(t[x].son,0,sizeof(t[x].son));24 t[x].fail=t[x].cnt=0;25 }26 27 void trie(int st)28 {29 int now=0;30 for(int i=1;i<=l;i++)31 {32 int ind=s[i]-'a'+1;33 if(!t[now].son[ind])34 {35 t[now].son[ind]=++tot;upd(tot);36 }37 now=t[now].son[ind];38 t[now].cnt++;39 if(i==l) bj[st]=now;40 }41 }42 43 queue q;44 stack sta;45 void build()46 {47 while(!q.empty()) q.pop();48 49 q.push(0);50 while(!q.empty())51 {52 int x=q.front();sta.push(x);53 q.pop();54 for(int i=1;i<=26;i++) if(t[x].son[i])55 {56 if(x&&t[t[x].fail].son[i]) t[t[x].son[i]].fail=t[t[x].fail].son[i];57 q.push(t[x].son[i]);58 }59 else t[x].son[i]=t[t[x].fail].son[i];60 }61 while(!sta.empty())62 {63 int x=sta.top();sta.pop();64 t[t[x].fail].cnt+=t[x].cnt;65 }66 }67 68 int main()69 {70 int n;71 scanf("%d",&n);72 tot=0;upd(0);73 for(int i=1;i<=n;i++)74 {75 scanf("%s",s+1);76 l=strlen(s+1);77 trie(i);78 }79 build();80 for(int i=1;i<=n;i++) printf("%d\n",t[bj[i]].cnt);81 return 0;82 }
WA了几次之后终于给面子A了【捂脸= =打模板而已嘛- -
多年前手打队列版本
1 #include2 #include 3 #include 4 5 const int Maxn=(int)1e4; 6 const int Maxl=200; 7 8 struct node 9 {10 int son[27],fail,cnt,ans;11 }t[160357];12 13 int n,m,cnt=0;14 int q[Maxn*Maxl+10],bj[Maxn];15 char s[Maxl];16 17 void floy()18 {19 int i;20 for(i=1;i<=Maxn;i++) t[i].fail=0,t[i].ans=0;21 }22 23 void read() 24 {25 memset(bj,0,sizeof(bj));26 int i,j,x,ind;27 scanf("%d",&n);28 getchar();29 for(i=1;i<=n;i++)30 {31 scanf("%s",s+1);32 m=strlen(s+1);33 x=0;34 for(j=1;j<=m;j++)35 {36 ind=s[j]-'a'+1;37 if(!t[x].son[ind]) t[x].son[ind]=++cnt;38 x=t[x].son[ind];39 t[x].cnt++;40 if(j==m) bj[i]=cnt;41 }42 }43 }44 45 void Build_AC()46 {47 int i,x,y,j;48 q[0]=0;49 q[++q[0]]=0;50 //for(i=1;i<=26;i++) if(t[0].son[i]) q[++q[0]]=t[0].son[i]; 51 for(i=1;i<=q[0];i++)52 {53 x=q[i];54 y=t[x].fail;55 for(j=1;j<=26;j++)56 if(t[x].son[j]) 57 { 58 //t[t[x].son[j]].fail=t[y].son[j];59 t[t[x].son[j]].fail=x?t[y].son[j]:x; 60 q[++q[0]]=t[x].son[j]; 61 }62 else t[x].son[j]=t[y].son[j];63 }64 for(i=q[0];i>=1;i--)65 {66 t[t[q[i]].fail].cnt+=t[q[i]].cnt;67 }68 //for(i=1;i<=cnt;i++) printf("%d %d %d %d\n",i,t[i].cnt,t[i].fail,t[i].ffail);69 }70 71 int main()72 {73 read();74 Build_AC();75 for(int i=1;i<=n;i++) printf("%d\n",t[bj[i]].cnt);76 return 0;77 }
AC自动机
2016-11-18 10:18:14