AC自动机：
·不要像以前一样习惯性把trie树的根设为1，从0开始的话后面getfail比较方便。
·trie树的节点编号是无序的，统计答案需要dfs或者拓扑，按编号循环显然是错的。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int S=2e6+10,N=2e5+10; int n,cnt[N],now,tot,len,tree[N][27],ed[N],num[N],fail[N]; char s[S]; int head[N],Next[N],tot1,ver[N],du[N]; void add(int x,int y){ ver[++tot1]=y; Next[tot1]=head[x]; head[x]=tot1; } void insert(int x){ now=0; len=strlen(s+1); for(int i=1;i<=len;i++){ if(!tree[now][s[i]-'a'])tree[now][s[i]-'a']=++tot; now=tree[now][s[i]-'a']; } ed[now]=1; cnt[x]=now; } queue<int>q; void getfail(){ for(int i=0;i<26;i++){ if(tree[0][i]){ fail[tree[0][i]]=0; q.push(tree[0][i]); add(tree[0][i],0); du[0]++; } } while(q.size()){ int u=q.front(); q.pop(); for(int i=0;i<26;i++){ int v=tree[u][i]; if(v){ fail[v]=tree[fail[u]][i]; q.push(v); add(v,fail[v]); du[fail[v]]++; } else{ tree[u][i]=tree[fail[u]][i]; } } } } void AC(){ now=0; len=strlen(s+1); for(int i=1;i<=len;i++){ int v=tree[now][s[i]-'a']; num[v]++; now=v; } } int main() { // freopen("1.in","r",stdin); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%s",s+1); insert(i); } getfail(); scanf("%s",s+1); AC(); for(int i=1;i<=tot;i++){ if(!du[i])q.push(i); } while(q.size()){ int u=q.front(); q.pop(); for(int i=head[u];i;i=Next[i]){ int y=ver[i]; num[y]+=num[u]; du[y]--; if(!du[y])q.push(y); } } for(int i=1;i<=n;i++){ printf("%d\n",num[cnt[i]]); } return 0; } /* 6 a bb aa abaa abaaa abaaa abaaabaa */
·跳fail能跳到危险节点的节点，自身必为危险节点。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; int n,now,tot,len,flag; char s[30010]; int tree[30010][2],ed[30010],fail[30010]; void insert(){ now=0; len=strlen(s+1); for(int i=1;i<=len;i++){ if(!tree[now][s[i]-'0'])tree[now][s[i]-'0']=++tot; now=tree[now][s[i]-'0']; } ed[now]=1; } queue<int>q; void getfail(){ for(int i=0;i<2;i++){ fail[tree[0][i]]=0; if(tree[0][i]){ q.push(tree[0][i]); } } while(!q.empty()){ int u=q.front(); q.pop(); for(int i=0;i<2;i++){ int v=tree[u][i]; if(v){ fail[v]=tree[fail[u]][i]; if(ed[fail[v]])ed[v]=1; q.push(v); } else tree[u][i]=tree[fail[u]][i]; } } } int vis[30010]; int dfs(int x){ if(flag)return 1; if(ed[x])return 0; if(vis[x])return 1; if(x)vis[x]=1; int val=(dfs(tree[x][0])|dfs(tree[x][1])); if(val)flag=1; vis[x]=0; return val; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%s",s+1); insert(); } getfail(); if(dfs(0))printf("TAK\n"); else printf("NIE\n"); return 0; } /* 3 011 11 00000 */
·trie树里很多走不到的字母相当于回到根，转移和统计带根一起算。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; int n,m; char s[110]; int now,len,tot,tree[6010][26],fail[6010],ed[6010]; void insert(){ now=0; len=strlen(s+1); for(int i=1;i<=len;i++){ if(!tree[now][s[i]-'A'])tree[now][s[i]-'A']=++tot; now=tree[now][s[i]-'A']; } ed[now]=1; } queue<int>q; void getfail(){ for(int i=0;i<26;i++){ if(tree[0][i]){ q.push(tree[0][i]); } } while(q.size()){ int u=q.front(); q.pop(); for(int i=0;i<26;i++){ int v=tree[u][i]; if(v){ fail[v]=tree[fail[u]][i]; q.push(v); if(ed[fail[v]])ed[v]=1; } else{ tree[u][i]=tree[fail[u]][i]; } } } } int f[110][6010],ans; void work(){ f[0][0]=1; for(int t=0;t<m;t++){ for(int i=0;i<=tot;i++){ if(ed[i])continue; for(int j=0;j<26;j++){ if(ed[tree[i][j]])continue; f[t+1][tree[i][j]]=(f[t+1][tree[i][j]]+f[t][i])%10007; } } } for(int i=0;i<=tot;i++)ans=(ans+f[m][i])%10007; } int ks(int x,int k){ int num=1; while(k){ if(k&1)num=num*x%10007; x=x*x%10007; k>>=1; } return num; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%s",s+1); insert(); } getfail(); work(); printf("%d\n",((ks(26,m)-ans)%10007+10007)%10007); return 0; }
回文自动机：
·注意细节
#include<iostream> #include<cstdio> #include<cstring> using namespace std; char s[23000010],a[11000010]; int len,lst=0,p[23000010],pos,ans; void manacher(){ for(int i=1;i<=len*2+1;i++){ if(lst<i){ pos=i; for(int j=i;j<=len*2+1&&2*i-j>0;j++){ if(s[j]!=s[2*i-j])break; p[i]++; lst=j; } } else{ int v=2*pos-i; if(i+p[v]-1>lst)p[i]=lst-i+1; else if(i+p[v]-1<lst)p[i]=p[v]; else{ p[i]=p[v]; while(s[i+p[i]]==s[i-p[i]])p[i]++; lst=i+p[i]-1; pos=i; } } } } int main() { scanf("%s",a+1); len=strlen(a+1); s[0]=s[1]='#'; for(int i=1;i<=len;i++){ s[i*2]=a[i]; s[i*2+1]='#'; } manacher(); for(int i=1;i<=2*len+1;i++)ans=max(ans,p[i]-1); printf("%d\n",ans); return 0; }