ZR 集训 Day21 – AC 自动机、回文树

ooliver 发布于 10 小时前 68 次阅读 OI

AI 摘要

从模板到病毒再到游戏，AC 自动机不只是多模式匹配利器——把无限串变成环，把 fail 链变成价值，甚至能陪你打游戏。准备好进入 Trie 图的世界了吗？

待办：

学习回文树。

AC 自动机与回文树例题若干。

题单：

P5357 【模板】AC 自动机

模板，上代码：

C++
#include<bits/stdc++.h>
using namespace std;

const int N=2e5+5;

struct ACAM{
    int tr[N][30];
    int fail[N],cnt[N],in[N],id[N],ask[N],ans[N];
    int midx,didx;
    void init(){
        midx=didx=0;
        clear(0);
    }
    void clear(int p){
        memset(tr[p],0,sizeof tr[p]);
        fail[p]=cnt[p]=in[p]=id[p]=0;
    }
    void insert(string s,int qid){
        int p=0;
        for(int i=0;i<s.size();i++){
            if(!tr[p][s[i]-'a']){
                tr[p][s[i]-'a']=++didx;
                clear(tr[p][s[i]-'a']);
            }
            p=tr[p][s[i]-'a'];
        }
        if(!id[p]) id[p]=++midx;
        ask[qid]=id[p];
    }
    void build(){
        queue<int> q;
        for(int i=0;i<26;i++) if(tr[0][i]) q.push(tr[0][i]);
        while(q.size()){
            int p=q.front();
            q.pop();
            for(int i=0;i<26;i++){
                if(tr[p][i]){
                    fail[tr[p][i]]=tr[fail[p]][i],in[tr[fail[p]][i]]++;
                    q.push(tr[p][i]);
                }
                else tr[p][i]=tr[fail[p]][i];
            }
        }
    }
    void query(string s){
        int p=0;
        for(int i=0;i<s.size();i++){
            p=tr[p][s[i]-'a'];
            cnt[p]++;
        }
    }
    void topu(){
        queue<int> q;
        for(int i=1;i<=didx;i++) if(!in[i]) q.push(i);
        while(q.size()){
            int p=q.front();
            q.pop();
            ans[id[p]]=cnt[p],cnt[fail[p]]+=cnt[p],in[fail[p]]--;
            if(!in[fail[p]]) q.push(fail[p]);
        }
    }
    int get(int qid){
        return ans[ask[qid]];
    }
}acam;

int main(){
    int n;
    string t,s;
    acam.init();
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>t;
        acam.insert(t,i);
    }
    acam.build();
    cin>>s;
    acam.query(s);
    acam.topu();
    for(int i=1;i<=n;i++) cout<<acam.get(i)<<"\n";
    return 0;
}

P2444 [POI 2000 R1] 病毒

首先，我们需要知道一个事情，那就是 AC 自动机构成的 Trie 图是一个完备的“确定性有限状态自动机”，用人话讲就是所有字符集内的有限串都是能在自动机里找到的。

题目里说的无限 01 串实际上可以看作是有限 01 串无限循环下去，映射到 Trie 图上就是一个环，所以我们构建 Trie 图后找环即可。

对于病毒串，我们在串尾打上病毒标记，找环时不走到这个状态即可。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

const int N=3e4+5;

struct ACAM{
    int tr[N][2];
    int fail[N],tag[N],dan[N];
    int didx;
    void init(){
        didx=0;
        clear(0);
    }
    void clear(int p){
        memset(tr[p],0,sizeof tr[p]);
        fail[p]=0;
    }
    void insert(string s){
        int p=0;
        for(int i=0;i<s.size();i++){
            if(!tr[p][s[i]-'0']){
                tr[p][s[i]-'0']=++didx;
                clear(tr[p][s[i]-'0']);
            }
            p=tr[p][s[i]-'0'];
        }
        dan[p]=1;
    }
    void build(){
        queue<int> q;
        for(int i=0;i<2;i++) if(tr[0][i]) q.push(tr[0][i]);
        while(q.size()){
            int p=q.front();
            q.pop();
            for(int i=0;i<2;i++){
                if(tr[p][i]){
                    fail[tr[p][i]]=tr[fail[p]][i];
                    q.push(tr[p][i]);
                    if(dan[tr[fail[p]][i]]) dan[tr[p][i]]=1;
                }
                else tr[p][i]=tr[fail[p]][i];
            }
        }
    }
    bool find(int u){
        if(tag[u]==1) return 1;
        if(tag[u]==-1) return 0;
        tag[u]=1;
        for(int i=0;i<2;i++) if(!dan[tr[u][i]]) if(find(tr[u][i])) return 1;
        tag[u]=-1;
        return 0;
    }
}acam;

int main(){
    int n;
    string t;
    acam.init();
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>t;
        acam.insert(t);
    }
    acam.build();
    if(acam.find(0)) cout<<"TAK";
    else cout<<"NIE";
    return 0;
}

P3041 [USACO12JAN] Video Game G

先对所有“组合技”串插入到自动机里，考虑一个状态的价值应该是其 fail 祖先链上的节点价值之和，我们在 build 的时候记录这样一个 $vis$ 数组，之后进行 DP，设 $dp_{i,j}$ 表示选了 $i$ 个字符，当前在 Trie 上的节点 $j$，有转移方程：

$$
dp_{i,tr[j][k]}=\max _{k\in \{'A','B','C'\}}(dp_{i,tr[j][k]},dp_{i-1,j}+vis_{tr[j][k]})
$$

代码：

C++
#include<bits/stdc++.h>
using namespace std;

const int N=305,M=1e3+5;

struct ACAM{
    int tr[N][3];
    int fail[N],vis[N],dp[M][N];
    int didx;
    void init(){
        didx=0;
        clear(0);
    }
    void clear(int p){
        memset(tr[p],0,sizeof tr[p]);
        fail[p]=vis[p]=0;
    }
    void insert(string s){
        int p=0;
        for(int i=0;i<s.size();i++){
            if(!tr[p][s[i]-'A']){
                tr[p][s[i]-'A']=++didx;
                clear(tr[p][s[i]-'A']);
            }
            p=tr[p][s[i]-'A'];
        }
        vis[p]++;
    }
    void build(){
        queue<int> q;
        for(int i=0;i<3;i++) if(tr[0][i]) q.push(tr[0][i]);
        while(q.size()){
            int p=q.front();
            q.pop();
            for(int i=0;i<3;i++){
                if(tr[p][i]){
                    fail[tr[p][i]]=tr[fail[p]][i];
                    vis[tr[p][i]]+=vis[tr[fail[p]][i]];
                    q.push(tr[p][i]);
                }
                else tr[p][i]=tr[fail[p]][i];
            }
        }
    }
    int getans(int k){
        int res=0;
        memset(dp,-0x3f,sizeof dp);
        dp[0][0]=0;
        for(int i=1;i<=k;i++) for(int j=0;j<=didx;j++) for(int l=0;l<3;l++){
            if(dp[i-1][j]<0) continue;
            dp[i][tr[j][l]]=max(dp[i][tr[j][l]],dp[i-1][j]+vis[tr[j][l]]);
        }
            
        for(int i=0;i<=didx;i++) res=max(res,dp[k][i]);
        return res; 
    }
}acam;

int main(){
    int n,k;
    string t;
    acam.init();
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>t;
        acam.insert(t);
    }
    acam.build();
    cout<<acam.getans(k);
    return 0;
}