AC自动机 例题

洛谷 P3699

输入n个单词，求每个单词在所有单词中出现的次数。
构造AC自动机，topu排序。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
typedef struct AC{
    int Trie[maxn][27],fail[maxn],mp[maxn],cnt;
    int times[maxn],in[maxn];
    void Insert(char *s,int len,int idx);
    void build();
    void topu();
    void output();
}AC_auto;
int n;
char s[maxn];
AC_auto ac;
int main(){
    scanf ("%d",&n);
    for (int i=1;i<=n;i++){
        scanf ("%s",s+1);
        ac.Insert(s,strlen(s+1),i);
    }
    ac.build();
    ac.output();
    return 0;
}
void AC_auto::Insert(char *s,int len,int idx){
    int root = 0;
    for (int i=1;i<=len;i++){
        if (!Trie[root][s[i]-'a'+1])    Trie[root][s[i]-'a'+1] = ++cnt;
        root = Trie[root][s[i]-'a'+1];
        times[root]++;
    }
    mp[idx] = root;
    return;
}
void AC_auto::build(){
    queue<int> q;
    for (int i=1;i<=26;i++) if (Trie[0][i])
        q.push(Trie[0][i]);
    while (!q.empty()){
        int temp = q.front();   q.pop();
        for (int i=1;i<=26;i++){
            if (Trie[temp][i]){
                fail[Trie[temp][i]] = Trie[fail[temp]][i];
                in[Trie[fail[temp]][i]]++;
                q.push(Trie[temp][i]);
            }else
                Trie[temp][i] = Trie[fail[temp]][i];
        }
    }
    topu();
    return;
}
void AC_auto::topu(){
    queue<int> q;
    for (int i=1;i<=cnt;i++)    if (in[i]==0)
        q.push(i);
    while (!q.empty()){
        int temp = q.front();   q.pop();
        times[fail[temp]] += times[temp];
        in[fail[temp]]--;
        if (in[fail[temp]]==0)
            q.push(fail[temp]);
    }
    return;
}
void AC_auto::output(){
    for (int i=1;i<=n;i++)
        printf ("%d\n",times[mp[i]]);
    return;
}

CSES1731 Word Combinations

给一个母串s和若干个模板串，求用这些模板串可以有多少种方式组合成母串。结果对1e9+7取模。

思路：对模板串建立AC自动机。dp[i]表示s的前i个字符有多少种组合方式。

然后用母串跑一遍自动机，若母串扫描到s[i]时，自动机上扫描到第x个结点，我们知道x结点对应的字符串是子串s[1...i]的最长后缀，然后沿着fail边每一个结点都是一个后缀，直至走到0结点。那么就暴力跳fail边，对于每个后缀结点x(x必须被标记为是一个模板串)，有：dp[i] += dp[i-Len[xx]]

初始化dp[0] = 1.

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5, mod = 1e9+7;
struct AC_Auto{
    int Trie[maxn][27], fail[maxn], Len[maxn], cnt;
    int vis[maxn];
    AC_Auto(){
        cnt = 0;
    }
    void insert(char *s, int len);
    void build();
    void query(char *s, int len);
}A;
char s[5005], t[maxn];
int n, len, dp[5005];

int main(){
    scanf ("%s %d", s+1, &n);
    len = strlen(s+1);
    for (int i=1; i<=n; i++){
        scanf ("%s", t+1);
        A.insert(t, strlen(t+1));
    }
    A.build();
    dp[0] = 1;
    A.query(s, len);
    printf ("%d", dp[len]);
    return 0;
}
void AC_Auto::insert(char *s, int len){
    int root = 0;
    for (int i=1; i<=len; i++){
        if (!Trie[root][s[i]-'a'+1])    Trie[root][s[i]-'a'+1] = ++cnt;
        root = Trie[root][s[i]-'a'+1];
    }
    Len[root] = len;
    vis[root] = 1;
    return;
}
void AC_Auto::build(){
    queue<int> q;
    for (int i=1; i<=26; i++)   if (Trie[0][i])
        q.push(Trie[0][i]);
    while (!q.empty()){
        int tmp = q.front();    q.pop();
        for (int i=1; i<=26; i++){
            if (Trie[tmp][i]){
                fail[Trie[tmp][i]] = Trie[fail[tmp]][i];
                q.push(Trie[tmp][i]);
            }else{
                Trie[tmp][i] = Trie[fail[tmp]][i];
            }
        }
    }
    return;
}
void AC_Auto::query(char *s, int len){
    int root = 0, tmp;
    for (int i=1; i<=len; i++){
        root = Trie[root][s[i]-'a'+1];
        tmp = root;
        while (tmp){
            if (vis[tmp])
                dp[i] = (dp[i]+dp[i-Len[tmp]])%mod;
            tmp = fail[tmp];
        }
    }
    return;
}