AC自动机(Automaton)

小小总结

0. 千万记住insert完以后要build!!!老是忘掉QAQ
1. insert函数就只是trie数的插入函数，可在结尾根据条件打一些标记
2. build函数(构建fail树)，主要利用BFS
3. match函数中跑fail树其实就是反复跑后缀
4. fail树上倒过来建树以后可以进行很多高端操作，比如阿狸的打字机(也许还能树剖一下QAQ)
5. match函数中跑fail树过程可以转化为打标记，而避免重复跑一个相同的后缀，常见优化(见下面的二次加强版板子题)
6. AC自动机常与数位DP结合，毕竟数字和字符串长得差不多

洛谷-P3808 简单板子题

//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1e5+10;
const int mod = 1e9+7;
const double eps = 1e-9;

int trie[maxn][26], cnt;
int e[maxn];
int fail[maxn];

void insert(char *s) {
    int p=0;
    for(int i=0; s[i]; ++i) {
        int k=s[i]-'a';
        if(!trie[p][k]) trie[p][k]=++cnt;
        p=trie[p][k];
    }
    e[p]++;
}

void build() {
    queue<int> q;
    memset(fail,0,sizeof(fail));
    for(int i=0; i<26; ++i) if(trie[0][i]) q.push(trie[0][i]);
    while(!q.empty()) {
        int k=q.front(); q.pop();
        for(int i=0; i<26; ++i) {
            if(trie[k][i]) {
                fail[trie[k][i]]=trie[fail[k]][i];
                q.push(trie[k][i]);
            }
            else trie[k][i]=trie[fail[k]][i];
        }
    }
}
int match(char *t) {
    int p=0, res=0;
    for(int i=0; t[i]; ++i) {
        p=trie[p][t[i]-'a'];
        for(int j=p; j&&~e[j]; j=fail[j]) res+=e[j], e[j]=-1;
    }
    return res;
}

char t[maxn];

int main() {
    //ios::sync_with_stdio(false);
    int n=read();
    for(int i=0; i<n; ++i) {
        scanf("%s", t);
        insert(t);
    }
    build();
    scanf("%s", t);
    printf("%d\n", match(t));
}

洛谷-P3796 加强板子题

//#pragma comment(linker, "/STACK:102400000,102400000") 
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0', c=getchar();
    return x;
}

const int maxn = 1e6+10;
const int mod = 1e9+7;
const double eps = 1e-9;

struct Result{
    int num, id;
    bool operator < (const Result &rhs) const{
        if(num==rhs.num) return id<rhs.id;
        return num>rhs.num;
    }
}res[151];

string l[151];

int trie[maxn][26], cnt;
int e[maxn];
int fail[maxn];

void init() {
    memset(trie,0,sizeof(trie));
    memset(e,0,sizeof(e));
    memset(fail,0,sizeof(fail));
    cnt=0;
}

void insert(int id) {
    int len=l[id].size();
    int p=0;
    for(int i=0; i<len; ++i) {
        int k=l[id][i]-'a';
        if(!trie[p][k]) trie[p][k]=++cnt;
        p=trie[p][k];
    }
    e[p]=id;
}

void build() {
    queue<int> q;
    memset(fail,0,sizeof(fail));
    for(int i=0; i<26; ++i) if(trie[0][i]) q.push(trie[0][i]);
    while(!q.empty()) {
        int k=q.front(); q.pop();
        for(int i=0; i<26; ++i) {
            if(trie[k][i]) {
                fail[trie[k][i]]=trie[fail[k]][i];
                q.push(trie[k][i]);
            }
            else trie[k][i]=trie[fail[k]][i];
        }
    }
}
void match(const string &t) {
    int len=t.size();
    int p=0;
    for(int i=0; i<len; ++i) {
        p=trie[p][t[i]-'a'];
        for(int j=p; j; j=fail[j]) res[e[j]].num++;
    }
}

int main() {
    //ios::sync_with_stdio(false);
    int n;
    while(cin>>n, n) {
        init();
        for(int i=1; i<=n; ++i) {
            cin>>l[i];
            insert(i);
            res[i].num=0;
            res[i].id=i;
        }
        build();
        cin>>l[0];
        match(l[0]);
        sort(res+1,res+1+n);
        printf("%d\n", res[1].num);
        for(int i=1; i<=n; ++i) {
            if(res[i].num==res[1].num) cout<<l[res[i].id]<<endl;
            else break;
        }
    }
}

洛谷-P5357 二次加强板子题

fail树(DAG)上拓扑排序加速跑fail的过程

//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 2e6+10;
const int mod = 1e9+7;
const double eps = 1e-9;

char s[maxn];
int trie[maxn*5][26], num[maxn*5], in[maxn*5], fail[maxn*5], cnt;
int pos[maxn];

void insert(int id) {
    int len=strlen(s), p=0;
    for(int i=0; i<len; ++i) {
        int k=s[i]-'a';
        if(!trie[p][k]) trie[p][k]=++cnt;
        p=trie[p][k];
    }
    pos[id]=p;
}

void build() {
    queue<int> q;
    for(int i=0; i<26; ++i) if(trie[0][i]) q.push(trie[0][i]);
    while(q.size()) {
        int now=q.front(); q.pop();
        for(int i=0; i<26; ++i) {
            if(trie[now][i]) {
                fail[trie[now][i]]=trie[fail[now]][i];
                in[trie[fail[now]][i]]++;
                q.push(trie[now][i]);
            }
            else trie[now][i]=trie[fail[now]][i];
        }
    }
}

void match() {
    int len=strlen(s), p=0;
    for(int i=0; i<len; ++i) {
        p=trie[p][s[i]-'a'];
        num[p]++;
    }
}

void solve() {
    queue<int> q;
    for(int i=0; i<=cnt; ++i) if(!in[i]) q.push(i);
    while(q.size()) {
        int now=q.front(); q.pop();
        num[fail[now]]+=num[now];
        if(--in[fail[now]]==0) q.push(fail[now]);
    }
}

int main() {
    //ios::sync_with_stdio(false);
    int n=read();
    for(int i=1; i<=n; ++i) { scanf("%s", s); insert(i); }
    build();
    scanf("%s", s);
    match();
    solve();
    for(int i=1; i<=n; ++i) printf("%d\n", num[pos[i]]);
}