【复制】题解:AT_abc362_g [ABC362G] Count Substring Query / AC 自动机学习笔记

· · 算法·理论

原稿:https://www.luogu.com.cn/article/uxz00lnh

前置知识:

AC 自动机,又称自动 AC 机,全称 Aho-Corasick automaton。

  1. 构造一棵 Trie 树。
  2. 构造 Fail 指针。
  3. 匹配。

这是你的前置知识,在此不做讲解。

代码:

void insert(string s,int now){
    int u=0;
    for(int i=0;i<s.size();i++){
        int c=s[i]-'a';
        if(!trie[u][c]) trie[u][c]=++cnt;
        u=trie[u][c];
    }
    if(!vis[u]) vis[u]=now;//记录每个字符串都在哪个位置。
    //因为可能有重复的字符串,所以把所有相同的字符串指向第一次出现的位置。
    rev[now]=vis[u];//反向的vis,方便最后输出。
}

Fail 指针指向 Trie 树中该路径的最长后缀。

如图,红色指针即为一些 Fail 指针,b__a 就是 ba

在本文我们不把 Fail 指针与 Kmp 数组作比较。

设当前节点为 utrie[f][c]=u

设深度小于 u 的所有结点的 Fail 指针都已求得。

  1. 如果 trie[fail[f]][c] 存在,则 fail[trie[f][c]]=trie[fail[f]][c]

证明:因为 fail[f]f 的后缀,所以 trie[fail[f]][c]trie[f][c],即 u 的后缀。

  1. 如果 trie[fail[f]][c] 不存在,那么我们继续找到 trie[fail[fail[f]]][c]。重复 1 的判断过程,一直跳 Fail 指针直到根结点。

证明:因为 fail[f]f 的后缀,fail[fail[f]]fail[f] 的后缀,所以 fail[fail[f]]f 的后缀,所以 trie[fail[fail[f]]][c]trie[f][c],即 u 的后缀。

  1. 如果跳到最后都没有,指向根节点。

代码细节:

  1. 求 Fail 要用 BFS。

证明:由于我们假设深度小于 u 的所有结点的 Fail 指针都已求得,跳 Fail 时节点深度也只会越来越小,所以求 Fail 要用 BFS。

  1. u,即 trie[f][c] 不存在,令 trie[f][c]=trie[fail[f]][c]

证明:因为 fail[f]f 的后缀,所以 trie[fail[f]][c]trie[f][c] 的后缀。由于我们 trie[f][c] 路径肯定比 trie[fail[f]][c] 路径要长,匹配了 trie[f][c] 路径一定能匹配 trie[fail[f]][c] 路径,所以不会影响答案。

好处:直接记录下一个能匹配的位置,压缩了跳 Fail 的路径,把 O(\log n) 的复杂度压缩到 O(1),不会被卡掉。

当然,如果 trie[fail[f]][c] 也不存在,那就无事发生了(即连回根节点)。

这个东西也是可以自指的。

代码:

void getfail(){
    queue<int>q;
    for(int i=0;i<26;i++){
        if(trie[0][i]) q.push(trie[0][i]);
    }
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++){
            if(trie[u][i]){
                fail[trie[u][i]]=trie[fail[u]][i];
                q.push(trie[u][i]);
                ins[trie[fail[u]][i]]++;//为后面的拓扑排序做准备。
            }
            else trie[u][i]=trie[fail[u]][i];//路径压缩。
        }
    }
}
```cpp void query(string t){ int u=0; for(int i=0;i<t.size();i++){ u=trie[u][t[i]-'a'];//此时的trie树已经被修改了,该步骤一定成立。 for(int j=u;j;j=fail[j]) ans[vis[j]]++; } } ``` 我们也可以只标记找到的节点,再用拓扑排序求出答案。 此部分代码需要结合拓扑排序部分代码理解。 代码: ```cpp void query(string t){ int u=0; for(int i=0;i<t.size();i++){ u=trie[u][t[i]-'a'];//此时的trie树已经被修改了,该步骤一定成立。 ans[u]++; } } ``` - Fail 树 又称失配树。 所有的 Fail 边构成一棵树。 证明: 1. Fail 边不会成环。 2. Fail 边的深度比当前节点的深度要小。 - 拓扑排序优化 由于所有的 Fail 边构成一棵树,所以可以对其进行拓扑排序,从而求得答案。 ```cpp void topu(){ queue<int>q; for(int i=1;i<=cnt;i++){ if(!ins[i]) q.push(i); } while(!q.empty()){ int u=q.front(); q.pop(); flag[vis[u]]=ans[u]; //统计每个字符串出现的次数,若vis[u]=0则代表该位置不是字符串的结尾。 int v=fail[u];//遍历失配树。 ans[v]+=ans[u];//下传答案。 //能够这样做的原因是:如果一个字符串出现了n次,那么它的后缀也会出现至少n次。 if(!(--ins[v])) q.push(v);//拓扑排序流程 } } ``` 到这里我们的答案就求出来了。 - 输出答案 很显然,输出 $flag[rev[i]]$。 ```cpp for(int i=1;i<=n;i++) cout<<flag[rev[i]]<<endl; ``` - 完整代码: ```cpp #include<bits/stdc++.h> using namespace std; int n,trie[5000001][27],fail[5000001],flag[5000001],rev[5000001],cnt,vis[5000001],ins[5000001],l,maxn,ans[500001]; string s[500001],t; void insert(string s,int now){ int u=0; for(int i=0;i<s.size();i++){ int c=s[i]-'a'; if(!trie[u][c]) trie[u][c]=++cnt; u=trie[u][c]; } if(!vis[u]) vis[u]=now; rev[now]=vis[u]; } void getfail(){ queue<int>q; for(int i=0;i<26;i++){ if(trie[0][i]) q.push(trie[0][i]); } while(q.size()){ int u=q.front(); q.pop(); for(int i=0;i<26;i++){ if(trie[u][i]){ fail[trie[u][i]]=trie[fail[u]][i]; q.push(trie[u][i]); ins[trie[fail[u]][i]]++; } else trie[u][i]=trie[fail[u]][i]; } } } void query(string t){ int u=0; for(int i=0;i<t.size();i++){ u=trie[u][t[i]-'a']; ans[u]++; } } void topu(){ queue<int>q; for(int i=1;i<=cnt;i++){ if(!ins[i]) q.push(i); } while(!q.empty()){ int u=q.front(); q.pop(); flag[vis[u]]=ans[u]; int v=fail[u]; ans[v]+=ans[u]; if(!(--ins[v])) q.push(v); } } int main(){ cin>>t; while(cin>>n&&n){ memset(trie,0,sizeof trie); memset(ans,0,sizeof ans); memset(fail,0,sizeof fail); memset(vis,0,sizeof vis); memset(flag,0,sizeof flag); cnt=0; l=0; for(int i=1;i<=n;i++){ cin>>s[i]; insert(s[i],i); } getfail(); query(t); topu(); for(int i=1;i<=n;i++) cout<<flag[rev[i]]<<endl; } } ```