AC自动机

· · 个人记录

前言

在学习AC自动机前，请确保已经学习并能熟练运用：

引入

在漫长的OI路途，我们难免要接触到一种叫字符串的东西。

在解决关于字符串的问题时，我们又难免要解决两个字符串匹配的问题，

比如，在一个字符串s中，字符串t出现了多少次 这些问题。（详见KMP匹配）

而在OI路途也不是一直可以一帆风顺的，万恶的出题人绝对不会总让你只匹配一个字符串，他们肯定要想方设法提高些难度，比如一个文本串匹配多个匹配串……

显然，这时候我们不可能对着那么多个字符串一个一个的做KMP，这时候就要用到本文的内容：AC自动机。

AC自动机

AC自动机是建立在字典树和KMP思想上的产物，从某种意义上来说，KMP匹配也是AC自动机的一种特殊情况（字典树只有一条链的时候）。

它通过建立所有匹配串的字典树，在每个节点建立失配指针fail来将各节点联系起来。

指针fail指向的是当前串最长后缀的节点，这样可以保证沿着fail一直跳下去，不会漏掉任何一个后缀节点。

在文本串匹配时，对于文本串的每一个前缀串，通过跳fail指针将其后缀串全部搜一遍，累加答案即可。

P3808 【模板】AC 自动机（简单版）

code：

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

const int maxn=1e6+5,maxs=1e6+5;

int n,f[maxs][27],root=0,cnt=0;
int add[maxs],fail[maxs];
string s;

void insert(string s) {
    int now=root;
    for(int i=0;i<s.size();i++) {
        int c=s[i]-'a';
        if(!f[now][c]) f[now][c]=++cnt;
        now=f[now][c];
    }
    add[now]++;
    return ;
}

void build() {
    queue<int>q;
    for(int i=0;i<26;i++)
        if(f[root][i]) q.push(f[root][i]);
    while(!q.empty()) {
        int now=q.front();
        q.pop();
        for(int i=0;i<26;i++)
            if(f[now][i]) {
                fail[f[now][i]]=f[fail[now]][i];
                q.push(f[now][i]);
            }
            else f[now][i]=f[fail[now]][i];
    }
    return ;
}

int query(string s) {
    int now=root,re=0;
    for(int i=0;i<s.size();i++) {
        now=f[now][s[i]-'a'];
        for(int j=now;j&&add[j]!=-1;j=fail[j])
            re+=add[j],add[j]=-1;
    }
    return re;
}

int main() {
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>s;
        insert(s);
    }
    build();
    cin>>s;
    cout<<query(s);
    return 0;
}

P5357 【模板】AC 自动机（二次加强版）

code：

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

const int maxn=2e5+5,maxs=2e5+5;

int n,ch[maxs][26],cnt=0,root=0,num[maxs],fail[maxs],idx[maxn];
string s[maxn],t;
vector<int>edge[maxs];

void insert(string s,int id) {
    int now=root;
    for(int i=0;i<s.size();i++) {
        int c=s[i]-'a';
        if(!ch[now][c]) ch[now][c]=++cnt;
        now=ch[now][c];
    }
    idx[id]=now;
    return ;
}

void build() {
    queue<int>q;
    for(int i=0;i<26;i++)
        if(ch[root][i]) q.push(ch[root][i]),edge[root].push_back(ch[root][i]);
    while(!q.empty()) {
        int now=q.front();
        q.pop();
        for(int i=0;i<26;i++) {
            if(ch[now][i]) {
                fail[ch[now][i]]=ch[fail[now]][i];
                edge[ch[fail[now]][i]].push_back(ch[now][i]);
                q.push(ch[now][i]);
            }
            else ch[now][i]=ch[fail[now]][i];
        }
    }
    return ;
}

void query(string s) {
    int now=root;
    for(int i=0;i<s.size();i++) {
        int c=s[i]-'a';
        now=ch[now][c];
        num[now]++;
    }
    return ;
}

void dfs(int now) {
    for(int i=0;i<edge[now].size();i++)
        dfs(edge[now][i]),num[now]+=num[edge[now][i]];
    return ;
}

int main() {
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>s[i],insert(s[i],i);
    build();
    cin>>t;
    query(t);
    dfs(root);
    for(int i=1;i<=n;i++)
        cout<<num[idx[i]]<<endl;
    return 0;
}