AC自动机

一定要会 trie，不一定要会 kmp。
作者是个 fw，有些话不是很标准，还请见谅。
为了方便，接下来的 AC，没有特殊表明，均表示 AC自动机。

我们直接引入一道题目 P5357。
这题就是标准的模板，从中，我们可以得到 AC 的作用：统计文本串内各个模式串的个数。

我们回忆一下 trie 的作用：判断一个字符串在不在一堆字符串里。
这和题目很像，我们想想怎么建这棵 trie。
我们要找模式串的个数，那么这个 trie 肯定就是模式串建起来的了。

接下来，我们会遇到下面的问题：

文本串很长，我们不可能把所有子串遍历一遍。
如果只遍历一遍，那么到一个节点没路了，怎么办。

对于第二个问题，我们需要一个新的路，这就是失配指针。

既然已经失配，我的前缀已经没用了。
所以，每个节点失配指针会指向该节点字符串的最长后缀。

为了代码好写，如果节点没有某个儿子，我们会把这个儿子设成它失配指针的节点的该儿子。

说一下怎么算答案。
我们遍历文本串，设一个变量像遍历 trie 一样一直走。
然后，每到一个节点，说明这个节点的字符串出现了一次，相应的，它的所有后缀也出现了一次。
所以我们从这个遍历失配指针增加答案，直到到根节点。

但是这样每次最少减一次深度，复杂度错误。
我们可以离线，最后拓扑一下即可。

这里给出例题代码。

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define FL(a,b,c) for(int a=(b),a##end=(c);a<=a##end;++a)
#define FR(a,b,c) for(int a=(b),a##end=(c);a>=a##end;--a)
#define lowbit(x) ((x)&-(x))
#define eb emplace_back
#define SZ(x) (int)((x).size())
#define ll long long
#define vt vector
#define ar(x) array<int,x>
#define PII pair<int, int>
#define max(a, b)({auto f7r=(a);auto j3h=(b);f7r<j3h?j3h:f7r;})
#define cmax(a, b)({auto j3h=(b);(j3h>a)&&(a=j3h);})
#define min(a, b)({auto f7r=(a);auto j3h=(b);f7r>j3h?j3h:f7r;})
#define cmin(a, b)({auto j3h=(b);(j3h<a)&&(a=j3h);})
constexpr int N = 2e6 + 10;
struct node{//fail 失配指针，end 是哪个模式串的终点，ans 表示文本串里该节点字符串的个数。
    int fail, end, son[27], ans;
    void clear(){fail = end = ans = 0, memset(son, 0, sizeof son);}
}AC[N];
char a[N];
int tot, Map[N], ans[N];//模式串可能重复。
void insert(char*a, int num){
    int u = 0;
    FL(i, 1, strlen(a + 1)){
        int &z = AC[u].son[a[i] - 'a'];
        if(!z)z = ++tot, AC[tot].clear();
        u = z;
    }
    if(!AC[u].end)AC[u].end = num;
    Map[num] = AC[u].end;
}
void get_fail(){//建立失配指针，特别妙。
    queue<int>q;
    FL(i, 0, 25)if(AC[0].son[i])q.push(AC[0].son[i]);
    while(!q.empty()){
        int u = q.front(), fail = AC[u].fail, *z;
        q.pop();
        FL(i, 0, 25)
            if(!(z = &AC[u].son[i], *z))*z = AC[fail].son[i];
            else AC[*z].fail = AC[fail].son[i], q.push(*z), in[AC[*z].fail]++;
    }
}
void query(char*a){//遍历 trie
    int u = 0;
    FL(i, 1, strlen(a + 1))
        u = AC[u].son[a[i] - 'a'], AC[u].ans++;
}
void bfs(){//拓扑
    queue<int>q;
    FL(i, 1, tot)if(!in[i])q.push(i);
    while(!q.empty()){
        int u = q.front(), v;
        q.pop(), ans[AC[u].end] = AC[u].ans;
        AC[v = AC[u].fail].ans += AC[u].ans;
        if(!--in[v])q.push(v);
    }
}
int32_t main(){
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    FL(i, 1, n)cin >> a + 1, insert(a, i);
    get_fail(), cin >> a + 1, query(a), bfs();
    FL(i, 1, n)cout << ans[Map[i]] << endl;
    return 0;
}