【学习笔记】ac自动机&fail树

  • 定义

    • 解决文本串和多个模式串匹配的问题；
    • 本质是由多个模式串形成的一个字典树，由tie的意义知道：trie上的每一个节点都是一个模式串的前缀；
    • 在trie上加入fail边，一个节点fail边指向这个节点所代表的前缀的最长后缀节点（除开自身的后缀）；
    • 也就是说如果x->y，那么y所代表的串是x所代表的串在trie上出现过的最大后缀；

  • 例子

    • （黑边为trie，红边为fail）
    • 以"hers","she","his","i"为例：

    • 原谅我的画图水平。。。如果有精通graphViz的求指点

  • 构造算法

    • 离线算法，先对所有模式串建出trie，同时可以用cnt表示一个节点的有模式串的个数；
    • 规定根节点为0，fl[0] = 0，0的直接儿子的fl[v]=0；
    • 一个节点的后缀可以由它trie树上的父亲转移而来，所以按照深度bfs；
    • 假设u->v之间的边为c；
    • 所以只需要沿着fl[u]，fl[fl[u]],...，一直往上跳，找到第一个有c边的u',那么v'就是v的fl；
    • 实际实现中可以将$ch[u][i]==0$补成$fl[u]$，避免暴力往上跳;
    •  1 int n,len,ch[N][26],sz,cnt[N],fl[N];
 2 char s[N];
 3 queue<int>q;
 4 void ins(){
 5     int u=0; 
 6     for(int i=0,c;i<len;i++){
 7         c=s[i]-'a';
 8         if(!ch[u][c])ch[u][c]=++sz;
 9         u=ch[u][c];
10     }
11     cnt[u]++;
12 }
13 void get_fl(){
14     fl[0]=0;
15     for(int i=0;i<26;i++)if(ch[0][i]){
16         fl[ch[0][i]]=0;
17         q.push(ch[0][i]);
18     }
19     while(!q.empty()){
20         int u=q.front();q.pop();
21         for(int i=0;i<26;i++){
22             int&v = ch[u][i];
23             if(!v){v=ch[fl[u]][i];continue;}
24             fl[v]=ch[fl[u]][i];
25             q.push(v);
26         }
27     }
28 }

  • 性质

    • 1.匹配

    • 文本串和模式串的匹配只需不断$u=ch[u][s[i]-'a']$即可；
    • 如果匹配到自动机的一个点，那么意味着沿着fail边走到的点都被匹配了；

    • 2.fail树

    • 由于一个点的fail指针唯一，且所有点的fail都和0连通，所以fail边形成了一个数的结构；
    • 沿着u的fail祖先往上走会找到u节点的所有后缀节点；
    • 对于字符串s，在自动机里匹配到的所有节点的所有fail祖先就表示s的所有子串；

  • 习题

    • 1.bzoj3172[Tjoi2013]单词
    • ac自动机模板，由于trie树上面只存储了前缀，子串的出现次数要按照深度从大到小对每个点向fail指针累加cnt; 
       1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<queue>
 6 #include<cmath>
 7 #include<vector>
 8 #include<stack>
 9 #include<map>
10 #include<set>
11 #define Run(i,l,r) for(int i=l;i<=r;i++)
12 #define Don(i,l,r) for(int i=l;i>=r;i--)
13 #define ll long long
14 #define ld long double
15 #define inf 0x3f3f3f3f
16 #define mk make_pair
17 #define fir first
18 #define sec second
19 #define il inline
20 #define rg register
21 #define pb push_back
22 using namespace std;
23 const int N=1000010;
24 int n,ch[N][26],sz,fl[N],sum[N],ans[N],id[N];
25 char s[N];
26 int q[N],t,w;
27 void ins(int now){
28     int l=strlen(s),u=0;
29     for(int i=0;i<l;i++){
30         int&v=ch[u][s[i]-'a'];
31         if(!v)v=++sz;
32         sum[u=v]++;
33     }
34     id[now]=u;
35 }
36 void solve(){
37     for(int i=0;i<26;i++){if(ch[0][i])q[++w]=ch[0][i];}
38     while(t<w){
39         int u=q[++t];
40         for(int i=0;i<26;i++){
41             int&v=ch[u][i];
42             if(!v)v=ch[fl[u]][i];
43             else fl[v]=ch[fl[u]][i],q[++w]=v;
44         }
45     }
46     for(int i=w;i;i--)sum[fl[q[i]]]+=sum[q[i]];
47     for(int i=1;i<=n;i++)printf("%d
",sum[id[i]]);
48 }
49 int main(){
50 //    freopen("bzoj3172.in","r",stdin);
51 //    freopen("bzoj3172.out","w",stdout);
52     scanf("%d",&n);
53     for(int i=1;i<=n;i++){scanf("%s",s);ins(i);}
54     solve();
55     return 0;
56 }//by tkys_Austin;
57
      bzoj3172
    • 2.bzoj1212[Hnoi2004]L语言
    • n，m都很小；$f[i]$表示前缀i是否可以被理解，$f[i]$可以从$f[j]（j<i）$转移的条件是$s[j+1]---S[i]$可以被理解，暴力判断应该会T
    • 对字典建自动机，如果把文章跑一遍，可以直接用fail指针暴力往上跳就可以找到所有的可以转移的j；  
       1 #include<bits/stdc++.h>
 2 #define rg register
 3 #define il inline
 4 using namespace std;
 5 const int N=1100010;
 6 int n,m,len,ch[N][26],sz,lst[N],head,tail,q[N],dep[N],vis[N],fl[N],ans;
 7 bool f[N];
 8 char s[N];
 9 il char gc(){
10     static char*p1,*p2,s[1000000];
11     if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);
12     return(p1==p2)?EOF:*p1++;
13 }
14 il int rd(){
15     int x=0;char c=gc();
16     while(c<'0'||c>'9')c=gc();
17     while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc();
18     return x;
19 }
20 il void gt(){
21     char *p = s,c = gc();
22     while(c<'a'||c>'z')c=gc();
23     while(c>='a'&&c<='z')*p++ = c,c=gc();
24     len = p - s;
25 }
26 il void ins(){
27     int u=0;
28     for(rg int i=0;i<len;i++){
29         if(!ch[u][s[i]-'a'])ch[u][s[i]-'a']=++sz;
30         u = ch[u][s[i]-'a'];
31     }
32     vis[u] = 1;
33 }
34 void get_fl(){
35     for(int i=0;i<26;i++)if(ch[0][i]){
36         q[++tail]=ch[0][i];
37         dep[ch[0][i]]=1;
38     }
39     while(head<tail){
40         int u=q[++head];
41         for(int i=0;i<26;i++){
42             int&v=ch[u][i];
43             if(!v){v=ch[fl[u]][i];continue;}
44             dep[v] = dep[u] + 1;
45             fl[v] = ch[fl[u]][i];
46             if(vis[fl[v]])lst[v]=fl[v];else lst[v]=lst[fl[v]];
47             q[++tail]=v;
48         }
49     }
50 }
51 il bool find(int x,int pos){
52     if(!x)return false;
53     if(vis[x]&&f[pos-dep[x]])return true;
54     return find(lst[x],pos);
55 } 
56 void query(){
57     f[0] = true;
58     for(rg int i=1,u=0;i<=len;i++){
59         u = ch[u][s[i-1]-'a'];
60         f[i] = find(u,i);
61         if(f[i]) ans = i;
62     }
63 }
64 int main(){
65     freopen("bzoj1212.in","r",stdin);
66     freopen("bzoj1212.out","w",stdout); 
67     n=rd();m=rd();
68     for(rg int i=1;i<=n;i++)gt(),ins();
69     get_fl(); 
70     for(rg int i=1;i<=m;i++){
71         gt();
72         memset(f,0,sizeof(bool)*(len+1));
73         ans = 0;
74         query();
75         printf("%d
",ans);
76     }
77     return 0;
78 }
      bzoj1212
    • 3.bzoj1030[Jsoi2007]文本生成器   (bzoj3530类似)
    • 如果直接问一个已知的文本是否含有给出单词就是模板题了；
    • 同样我们只关心给出的模板串，对模板建自动机做dp
    • $dp[i][j]$表示生成了前$i$位，当前匹配状态为自动机的$j$号节点；
    • 新开一个节点统计答案，每次都自乘*26；
    • 枚举下一个字符k,考虑转移到ch[j][k] , 注意如果ch[j][k]是一个已经匹配了单词的节点就直接转移到统计答案的节点
    • 初始f[0][0]=1;
    • O(N*Len)某些情况下可写成矩阵乘法转移
    • 我写的时候犯了点错：

    • 但是ac自动机的匹配算法中，注意所有匹配走过路径的节点并不是所有的单词节点，因为可能会有中间匹配点可以按照失配边走到有串的节点，所以代码里vis要沿fail向下传递；

       1 #include<bits/stdc++.h>
 2 #define rg register
 3 #define il inline
 4 using namespace std;
 5 const int N=61,M=110,mod=10007;
 6 int n,m,ch[N*M][26],f[M][N*M],vis[N*M],fl[N*M],head,tail,q[N*M],sz;
 7 char s[M];
 8 il void ins(){
 9     int l = strlen(s) , u=0;
10     for(rg int i=0;i<l;i++){
11         int& v = ch[u][s[i]-'A'];
12         if(!v)v = ++sz;
13         u = v;
14     }
15     vis[u]=1;
16 }
17 void get_fl(){
18     for(int i=0;i<26;i++)if(ch[0][i])q[++tail]=ch[0][i];
19     while(head<tail){
20         int u = q[++head];
21         for(rg int i=0;i<26;i++){
22             int& v=ch[u][i];
23             if(!v){v=ch[fl[u]][i];continue;}
24             fl[v]=ch[fl[u]][i];
25             q[++tail]=v;
26         }
27     }
28     for(rg int i=1;i<=tail;i++)vis[q[i]] |= vis[fl[q[i]]];
29 }
30 il void upd(int&x,int y){x+=y;if(x>=mod)x-=mod;}
31 int main(){
32     freopen("bzoj1030.in","r",stdin);
33     freopen("bzoj1030.out","w",stdout);
34     scanf("%d%d",&n,&m);
35     for(rg int i=1;i<=n;i++){scanf("%s",s);ins();}
36     get_fl();
37     f[0][0]=1;
38     for(rg int i=0;i<m;i++){
39         for(rg int j=0;j<=sz;j++){
40             for(rg int k=0;k<26;k++){
41                 if(vis[ch[j][k]])upd(f[i+1][sz+1],f[i][j]);
42                 else upd(f[i+1][ch[j][k]],f[i][j]);
43             }
44         }
45         upd(f[i+1][sz+1],f[i][sz+1]*26%mod);
46     }
47     cout<<f[m][sz+1]<<endl;
48     return 0;
49 }
      bzoj1030
    • 4.bzoj1444[Jsoi2009]有趣的游戏
    • https://www.cnblogs.com/clrs97/p/4987277.html     ORZ
    • 不妨吧trie树上的有单词的节点叫做关键点，其他是非关键点；
    • 这题有意思的地方在于只能在关键点停下来；
    • 直接的想法是：用自动机建立概率方程，每个点的概率等于所有指向它的节点贡献之和，同时关键点不让转移(即不贡献出边)；
    • 然而这样也没有常数项。。。。。。。解出来都是0？？？！接下来的操作比较神奇：
    • 把0号点的方程(也有人说随意那个)用所有关键点概率之和==0替换再高斯消元即可,小心会输出-0.00所以要特判一下；
    • （如果有更好的理解希望指点，感激不尽） 
       1 #include<bits/stdc++.h>
 2 #define ld double
 3 #define rg register
 4 #define il inline
 5 using namespace std;
 6 const int N=110;
 7 int n,l,m,sz,id[N],vis[N],fl[N],q[N],t,w,ch[N][26],px[N],py[N];
 8 ld p[N],a[N][N]; 
 9 char s[N]; 
10 void get_fl(){
11     for(int i=0;i<m;i++)if(ch[0][i])q[++w]=ch[0][i];
12     while(t<w){
13         int u = q[++t];
14         for(int i=0;i<m;i++){
15             int&v = ch[u][i];
16             if(!v){v=ch[fl[u]][i];continue;}
17             fl[v]=ch[fl[u]][i];
18             q[++w]=v;
19         }
20     }
21     a[0][sz+1]=1;
22     for(int i=0;i<=sz;i++){
23         if(i)a[i][i]=1;
24         if(vis[i]){a[0][i]=1;continue;}
25         for(int j=0;j<m;j++)if(px[j]){
26             int v = ch[i][j];
27             if(v)a[v][i] -= p[j];
28         }
29     }
30 }
31 void gauss(){
32     for(rg int i=0;i<=sz;i++){
33         int pos=i;
34         for(rg int j=i+1;j<=sz;j++)if(fabs(a[j][i])>fabs(a[pos][i]))pos=j;
35         if(pos!=i)for(rg int j=i;j<=sz+1;j++)swap(a[i][j],a[pos][j]);
36         for(rg int j=i+1;j<=sz;j++){
37             ld tmp = a[j][i] / a[i][i];
38             for(rg int k=i;k<=sz+1;k++)a[j][k] -= tmp * a[i][k];
39         }
40     }
41     for(rg int i=sz;~i;i--){
42         for(rg int j=i+1;j<=sz;j++)a[i][sz+1] -= a[j][sz+1] * a[i][j];
43         a[i][sz+1] /= a[i][i]; 
44     }
45 }
46 int main(){
47     freopen("bzoj1444.in","r",stdin);
48     freopen("bzoj1444.out","w",stdout);
49     scanf("%d%d%d",&n,&l,&m);
50     for(int i=0;i<m;i++){
51         scanf("%d%d",&px[i],&py[i]);
52         p[i] = 1.0 * px[i] / py[i];
53     }
54     for(int i=1;i<=n;i++){
55         scanf("%s",s);
56         int u=0;
57         for(int j=0;j<l;j++){
58             if(!ch[u][s[j]-'A'])ch[u][s[j]-'A']=++sz;
59             u = ch[u][s[j]-'A'];
60         }
61         id[i] = u; vis[u] = 1;
62     }
63     get_fl();
64     gauss();
65     for(int i=1;i<=n;i++){
66         ld x = fabs(a[id[i]][sz+1]); 
67     //    x = fabs(-0.00);
68         if(x>0)printf("%.2lf
",x);
69         else puts("0.00");
70     }
71     return 0;
72 }
      bzoj1444
    • 5.bzoj2434[Noi2011]阿狸的打字机
    • 模拟操作建自动机，考虑现在有一颗trie树和fail树
    • x在y里面出现的次数 == 在trie树上y的所有祖先 在x在fail树上的子树里的有多少个
    • 维护这可以直接在trie上dfs，树状数组区间修改维护当前点到trie的根再fail树的dfs序，查询子树信息；
    • 或者直接对trie树链剖建主席树，权值是fail树的dfs序； 
        1 #include<bits/stdc++.h>
  2 #define rg register
  3 #define il inline 
  4 #define pb push_back
  5 using namespace std;
  6 const int N=100010,M=20;
  7 int n,m,ch[N][26],fa[N],tot,cnt,que[N],head,tail,fl[N],a[N];
  8 int id[N],pos[N],st[N],ed[N],sum[N*M],sz,tp[N],idx,son[N],size[N],rt[N],ls[N*M],rs[N*M];
  9 vector<int>g[N];
 10 char s[N];
 11 il char gc(){
 12     static char *p1,*p2,s[1000000];
 13     if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);
 14     return(p1==p2)?EOF:*p1++;
 15 }
 16 il int rd(){
 17     int x=0; char c=gc();
 18     while(c<'0'||c>'9')c=gc();
 19     while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc();
 20     return x;
 21 }
 22 il int gt(){
 23     char*p = s , c = gc();
 24     while(!isalpha(c))c=gc();
 25     while(isalpha(c))*p++=c,c=gc();
 26     return p - s; 
 27 }
 28 void get_fl(){
 29     for(int i=0;i<26;i++)if(ch[0][i]){
 30         que[++tail]=ch[0][i];
 31         g[0].pb(ch[0][i]);
 32     }
 33     while(head<tail){
 34         int u=que[++head];
 35         for(int i=0;i<26;i++){
 36             int& v=ch[u][i];
 37             if(!v){v=ch[fl[u]][i];continue;}
 38             fl[v]=ch[fl[u]][i];
 39             g[fl[v]].pb(v);
 40             que[++tail] = v;
 41         }
 42     }
 43 }
 44 void dfs1(int u){
 45     size[u]=1;son[u]=0;
 46     for(int i=0;i<26;i++){
 47         int v = ch[u][i];
 48         if(!v||v==fa[u])continue;
 49         dfs1(v); 
 50         size[u]+=size[v];
 51         if(!son[u]||size[v]>size[son[u]])son[u]=v;
 52     }
 53 }
 54 void dfs2(int u,int top){
 55     a[pos[u]=++idx]=u;
 56     tp[u]=top;
 57     if(son[u])dfs2(son[u],top);
 58     for(int i=0;i<26;i++){
 59         int v=ch[u][i];
 60         if(!v||v==fa[u]||v==son[u])continue;
 61         dfs2(v,v);
 62     }
 63 }
 64 void dfs(int u){
 65     st[u] = ++idx;
 66     for(int i=0;i<(int)g[u].size();i++){
 67         int v = g[u][i];
 68         dfs(v);
 69     }
 70     ed[u] = idx;
 71 }
 72 il void ins(int&k,int lst,int l,int r,int x,int y){
 73     sum[k=++sz]=sum[lst]+y;
 74     ls[k]=ls[lst];rs[k]=rs[lst];
 75     if(l==r)return ;
 76     int mid=(l+r)>>1;
 77     if(x<=mid)ins(ls[k],ls[lst],l,mid,x,y);
 78     else ins(rs[k],rs[lst],mid+1,r,x,y);
 79 }
 80 il int query(int k,int lst,int l,int r,int x,int y){
 81     if(l==x&&r==y)return sum[k]-sum[lst];
 82     else{
 83         int mid=(l+r)>>1;
 84         if(y<=mid)return query(ls[k],ls[lst],l,mid,x,y);
 85         else if(x>mid)return query(rs[k],rs[lst],mid+1,r,x,y);
 86         else return query(ls[k],ls[lst],l,mid,x,mid)+query(rs[k],rs[lst],mid+1,r,mid+1,y);
 87     }
 88 }
 89 il int Query(int x,int y){
 90     int re=0;
 91     while(~x){
 92         re += query(rt[pos[x]],rt[pos[tp[x]]-1],1,cnt,st[y],ed[y]);
 93         x = fa[tp[x]];
 94     }
 95     return re;
 96 }
 97 int main(){
 98     freopen("bzoj2434.in","r",stdin);
 99     freopen("bzoj2434.out","w",stdout);
100     n=gt();
101     int u = 0;
102     for(rg int i=0;i<n;i++){
103         if(s[i]=='B')u = fa[u];
104         else if(s[i]=='P')id[++tot] = u;
105         else {
106             if(!ch[u][s[i]-'a'])ch[u][s[i]-'a']=++cnt;
107             fa[ch[u][s[i]-'a']] = u;
108             u = ch[u][s[i]-'a'];
109         }
110     }
111     fa[0]=-1;
112     dfs1(0);
113     dfs2(0,0);
114     get_fl();
115     idx=0;dfs(0);
116     cnt++;
117     for(rg int i=1;i<=cnt;i++){ins(rt[i],rt[i-1],1,cnt,st[a[i]],1);}
118     m = rd();
119     for(rg int i=1,x,y;i<=m;i++){
120         x = rd() , y=rd();
121         int ans = Query(id[y],id[x]);
122         printf("%d
",ans);
123     }
124     return 0;
125 }
      bzoj2434
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Paul-Guderian/p/10217205.html