【题目来源】
https://www.luogu.com.cn/problem/P3966

【题目描述】
小张最近在忙毕设，所以一直在读论文。一篇论文是由许多单词组成的，但小张发现一个单词会在论文中出现很多次，他想知道每个单词分别在论文中出现了多少次。

【输入格式】
第一行一个整数 N，表示这篇文章有 N 个单词。
接下来 N 行每行一个单词，每个单词都由小写字母 a∼z 组成。

【输出格式】
输出 N 个整数，第 i 行的数表示第 i 个单词在文章中出现了多少次。

【输入样例】
3
a
aa
aaa

【输出样例】
6
3
1

【数据范围】
30% 的数据，单词总长度不超过 10^3。
100% 的数据，1≤n≤200，单词总长度不超过 10^6。

【算法分析】
（一）Trie树
● 除根结点外，字典树的每个结点只包含一个字符。
● Trie树中每个节点都有一个编号。Trie树的根节点为空节点，‌编号‌为 0。其他节点的编号通过全局自增变量 idx 动态分配。节点编号是‌动态分配给节点的唯一标识‌，仅依赖节点插入顺序，与节点所示字符的字典序无关。
（1）sn[p][u] 表示编号为 p 的节点的第 u 个子节点的编号（u 是字符 'a'-'z' 映射到数字 0-25 的索引）。
（2）cnt[p] 表示以编号为 p 的节点结尾的字符串个数。
● 字典树在实现时，会对每个字符串的结尾设置标记。

（二）AC 自动机
● AC 自动机（Aho-Corasick automaton）是一种字符串多模匹配算法，由 Alfred V. Aho 和 Margaret J. Corasick 于 1975 年在贝尔实验室提出‌。其核心思想结合了字典树（Trie）和 KMP 算法，能够高效地在文本中同时匹配多个模式串‌。即：AC自动机≈Trie+KMP。

● AC 自动机构建 fail 指针的过程采用广度优先搜索（BFS）策略，从 Trie 树的根节点开始逐层处理，确保父子关系正确。fail 指针采用 ne[] 数组进行存储。fail 指针的构建规则：“孩子节点的 fail 指针，指向双亲节点的 fail 指针指向的节点的同名孩子”。

● AC 自动机构建 fail 指针的过程如下：
（1）Trie 树根节点及其直接子节点的 fail 指针处理
Trie 树根节点（0 号节点）及其直接子节点的 fail 指针均指向根节点。这些节点构成 BFS 的初始队列。
（2）Trie 树其他节点的 fail 指针处理
依据 fail 指针的构建规则：“孩子节点的 fail 指针，指向双亲节点的 fail 指针指向的节点的同名孩子”。
在 Trie 树中，设当前节点的编号为 t，若其第 i 个孩子的节点编号为 x=sn[t][i]，则 ne[x]=sn[ne[t]][i]。如果 sn[ne[t]][i] 不存在，继续向上找 fail 指针的 fail 指针，直到找到对应字符的节点或根节点。（上文所言“同名孩子”的确定，是由 sn[][i] 数组的第 2 维 i 确定的。因为 i 是字符 'a'-'z' 映射到数字 0-25 的索引，故若 i 相同，说明是由相同的字符映射得到的）。
（3）路径压缩优化
如果当前节点的某个字符分支不存在直接子节点，则将该分支直接指向当前节点 fail 指针对应节点的相同字符分支。这种优化避免了匹配过程中的回溯，使得每个字符输入都能直接确定下一个状态。
（4）算法终止
当 BFS 队列为空时，所有节点的 fail 指针构建完成。此时 AC 自动机具备了在匹配失败时快速跳转的能力，类似于 KMP 算法中的 next 数组功能。
构建完成的 fail 指针确保每个节点都指向一个拥有最长公共后缀的节点，当匹配失败时能迅速跳转到可能匹配的位置继续匹配过程。

【算法代码一】

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

const int maxn=1e6+5;
int sn[maxn][26],idx;
int cnt[maxn],ne[maxn];
int q[maxn],pos[maxn];

void insert(string s,int id) { //Trie
    int p=0; //root=0
    for(int i=0; i<s.size(); i++) {
        int u=s[i]-'a';
        if(!sn[p][u]) sn[p][u]=++idx;
        p=sn[p][u];
        cnt[p]++;
    }
    pos[id]=p;
}

void build() { //AC automation
    int head=1,tail=0;
    for(int i=0; i<26; i++) {
        if(sn[0][i]) q[++tail]=sn[0][i];
    }

    while(head<=tail) {
        int u=q[head++];
        for(int i=0; i<26; i++) {
            int j=sn[u][i];
            if(j) {
                ne[j]=sn[ne[u]][i];
                q[++tail]=sn[u][i];
            } else sn[u][i]=sn[ne[u]][i];
        }
    }
}

int main() {
    string s;
    int n;
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>s;
        insert(s,i);
    }
    build();

    for(int i=idx; i>=1; i--) {
        cnt[ne[q[i]]]+=cnt[q[i]];
    }
    for(int i=1; i<=n; i++) {
        cout<<cnt[pos[i]]<<"\n";
    }

    return 0;
}

/*
in:
3
a
aa
aaa

out:
6
3
1
*/

【算法代码二】

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

const int maxn=1e6+5;
int sn[maxn][26],idx;
int cnt[maxn],ne[maxn];
int pos[maxn],deg[maxn];

void insert(string s,int id) { //Trie
    int p=0; //root=0
    for(int i=0; i<s.size(); i++) {
        int u=s[i]-'a';
        if(!sn[p][u]) sn[p][u]=++idx;
        p=sn[p][u];
        cnt[p]++;
    }
    pos[id]=p;
}

void build() { //AC automation
    queue<int> q;
    for(int i=0; i<26; i++) {
        if(sn[0][i]) q.push(sn[0][i]);
    }

    while(!q.empty()) {
        int u=q.front();
        q.pop();
        for(int i=0; i<26; i++) {
            int j=sn[u][i];
            if(j) {
                ne[j]=sn[ne[u]][i];
                q.push(j);
                deg[ne[j]]++;
            } else sn[u][i]=sn[ne[u]][i];
        }
    }
}

void topo() {
    queue<int> q;
    for(int i=1; i<=idx; i++) {
        if(!deg[i]) q.push(i);
    }
    while(!q.empty()) {
        int t=q.front();
        q.pop();
        cnt[ne[t]]+=cnt[t];
        deg[ne[t]]--;
        if(!deg[ne[t]]) q.push(ne[t]);
    }
}

int main() {
    string s;
    int n;
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>s;
        insert(s,i);
    }
    build();

    topo();
    for(int i=1; i<=n; i++) {
        cout<<cnt[pos[i]]<<"\n";
    }

    return 0;
}

/*
in:
3
a
aa
aaa

out:
6
3
1
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/153745058
https://www.cnblogs.com/Sinktank/p/18355554
https://www.luogu.com.cn/problem/P3796
https://www.luogu.com.cn/problem/P3966
https://www.cnblogs.com/wans-caesar-02111007/p/9806602.html
http://oi-wiki.com/string/ac-automaton/
https://blog.csdn.net/hnjzsyjyj/article/details/138599488
https://blog.csdn.net/hnjzsyjyj/article/details/138659402
https://blog.csdn.net/hnjzsyjyj/article/details/153636421
https://mp.weixin.qq.com/s/FGLnUpZ02WFg40oL0uG7Vg