AC自动机学习笔记

AAA404 · 2023-08-01 20:59:23 · 个人记录

基础的AC自动机我不讲，自行学习

这篇文章具体讲一下各种题目要求的实现和AC自动机上dp（画大饼）

（以下代码中 AC[a].vis[b] 表示AC自动机中的 a 节点的子节点中代表字符 b 的节点编号）

Part 1 AC自动机题目常见的问法

1.某些字符串是否出现（雾

说好的不讲模板，自行学习

2.某（些）字符串出现次数

将 insert 即插入函数和 query 求值函数修改即可

代码：

//插入函数
inline void insert(string s,int idd)
{
    int l=s.length();
    int now=0;
    for(int i=0;i<l;i++)
    {
        if(AC[now].vis[s[i]-'a']==0)
        AC[now].vis[s[i]-'a']=++cnt;
        now=AC[now].vis[s[i]-'a'];
    }
    //这两行改就行了，这里处理了重复串情况
    if(AC[now].end==0)AC[now].end=idd;
    id[idd]=AC[now].end;
    return;
}

//求值函数
//朴素版
inline void query(string s)
{
    int l=s.length();
    int now=0;
    for(int i=0;i<l;i++)
    {
        now=AC[now].vis[s[i]-'a'];
        for(int t=now;t;t=AC[t].fail)
        {
            if(AC[t].end)num[id[AC[t].end]]++;
        }
    }
    return;
}
//拓扑排序优化版
inline void query(string s)
{
    int l=s.length();
    int now=0;
    for(int i=0;i<l;i++)
    {
        now=AC[now].vis[s[i]-'a'];
        vis[now]++;
    }
    topo();
    for(int i=1;i<=cnt;i++)
    {
        if(AC[i].end)ans[AC[i].end]=vis[i];
    }
}

拓扑排序优化背板子就好了（逃

3.（其实是 2 的一个子问题）某个（些）字符串出现次数最多

这个在 2 的基础上加些处理就好了

4.还是讲下拓扑优化吧

就是一个拓扑排序的板子......吧

在求 fail 指针时预处理，然后掏出下面的板子：

inline void topo()
{
    queue<int>q;
    for(int i=0;i<=cnt;i++)
    {
        if(!in[i])q.push(i);
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[AC[u].fail]+=vis[u];
        if(--in[AC[u].fail]==0)
        {
            q.push(AC[u].fail);
        }
    }
    return;
}

求 fail 时的预处理（核心代码）：

while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++)
        {
            if(AC[u].vis[i]!=0)
            {
                AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i];
                in[AC[AC[u].fail].vis[i]]++;//只多了这一行
                q.push(AC[u].vis[i]);
            }
            else AC[u].vis[i]=AC[AC[u].fail].vis[i];
        }
    }

然后用 query 的那个带优化的板子就行了

Part 1.5 fail树

因为学AC自动机上dp时发现 fail 树是一个很重要的东西，故略提一下

思考 fail 指针的本质：跳转至与当前串有相同后缀的串的跳转指针

（语文不好解释起来很拗口，可以自行 bdfs ）

在构建 fail 指针时，我们将 Trie 树补全成为了一张有向图，可以叫 Trie 图

那么就可以在AC自动机上进行图上操作

例题：P2444

这道题的安全代码在AC自动机上匹配永远无法匹配成功（如果匹配成功就包含了病毒），所以就会在匹配中一直在AC自动机中跳

所以就是在有向图中求一个环，使得环上不存在病毒串的末尾节点， 大法师即可

代码：

#include<bits/stdc++.h>
using namespace std;
const int M=3e4+5;
int n,cnt;
string s;
bool in[M],vis[M];
struct node{
    int vis[2];
    int end;
    int fail;
}AC[M];
inline void insert(string s)
{
    int l=s.length();
    int now=0;
    for(int i=0;i<l;i++)
    {
        if(AC[now].vis[s[i]-'0']==0)
        AC[now].vis[s[i]-'0']=++cnt;
        now=AC[now].vis[s[i]-'0'];
    }
    AC[now].end++;
    return;
}
inline void get_fail()
{
    queue<int>q;
    for(int i=0;i<2;i++)
    {
        if(AC[0].vis[i]!=0)
        {
            AC[AC[0].vis[i]].fail=0;
            q.push(AC[0].vis[i]);
        }
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<2;i++)
        {
            if(AC[u].vis[i]!=0)
            {
                AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i];
                q.push(AC[u].vis[i]);
            }
            else AC[u].vis[i]=AC[AC[u].fail].vis[i];
        }
        AC[u].end+=AC[AC[u].fail].end;//如果一个点的fail不能在环上，那么它也不能在环上
    }
    return;
}
inline void dfs(int p)//求有向图中的环
{
    if(in[p]){cout<<"TAK";exit(0);}//找到直接结束
    if(vis[p]||AC[p].end)return;
    in[p]=vis[p]=1;
    dfs(AC[p].vis[0]);
    dfs(AC[p].vis[1]);
    in[p]=0;
    return;
}
int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        insert(s);
    }
    get_fail();
    dfs(0);
    cout<<"NIE";
    return 0;
}

Part 2 AC自动机上dp

AC自动机上的dp一般是二维的

那么最终的答案就是：26^m - \sum f[m][i]

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=105,M=6005,mod=1e4+7;
int n,m,cnt,f[N][M],ans=1,sum;
string s;
struct node{
    int vis[26];
    int end;
    int fail;
}AC[M];
inline void insert(string s)
{
    int l=s.length();
    int now=0;
    for(int i=0;i<l;i++)
    {
        if(AC[now].vis[s[i]-'A']==0)
        AC[now].vis[s[i]-'A']=++cnt;
        now=AC[now].vis[s[i]-'A'];
    }
    AC[now].end++;
    return;
}
inline void get_fail()
{
    queue<int>q;
    for(int i=0;i<26;i++)
    {
        if(AC[0].vis[i]!=0)
        {
            AC[AC[0].vis[i]].fail=0;
            q.push(AC[0].vis[i]);
        }
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=0;i<26;i++)
        {
            if(AC[u].vis[i]!=0)
            {
                AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i];
                q.push(AC[u].vis[i]);
            }
            else AC[u].vis[i]=AC[AC[u].fail].vis[i];
        }
        AC[u].end+=AC[AC[u].fail].end;//参见Part 1.5
    }
    return;
}
int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        insert(s);
    }
    get_fail();
    f[0][0]=1;
    for(int i=0;i<=m-1;i++)
    {
        for(int j=0;j<=cnt;j++)
        {
            for(int k=0;k<26;k++)
            {
                if(AC[AC[j].vis[k]].end==0)//如果不是结尾
                (f[i+1][AC[j].vis[k]]+=f[i][j])%=mod;
            }
        }
    }
    for(int i=1;i<=m;i++)(ans*=26)%=mod;//暴力美学
    for(int i=0;i<=cnt;i++)
    {
        (sum+=f[m][i])%=mod;
    }
    cout<<(ans-sum+mod)%mod;
    return 0;
}

先写这点，还在研究矩阵快速幂优化