前言
公约：
- 字符串默认下标从 0 开始
- $s[l\dots r]$ 表示字符串 $s$ 的一个子串 $s_l s_{l+1} s_{l+2} \dots s_r$
- 默认字符集为小写字母
KMP
前缀数组
给定字符串 $s$，其前缀数组 $\pi$ 的定义为：
$\pi_i$ 是是得 $s[i-k+1\dots i]=s[0\dots k-1]$ 且 $k\lt i$ 的最大的 $k$。
形式化的讲，就是求每个前缀中真前缀和真后缀相等的最长前缀（后缀）长度。
Border
我们称一个字符串中，若有一个真前缀能与一个真后缀相等则称该真前缀为字符串的一个 Border。一个字符串可能有多个 Border，空串也算一个 Border。
KMP
依旧假设我们已知 $\pi_0\dots \pi_{i-1}$，来求 $\pi_i$。若 $t$ 是该前缀的一个 Border，则将 $t$ 的最后一个字符去掉后得到的 $t’$ 一定是 $s[0\dots i-1]$ 的一个 Border。所以如果 $s_{\pi_{i-1}}=s_i$，则该前缀的 Border 的最长长度一定为 $\pi_{i-1}+1$。
如果 $s_{\pi_{i-1}}\neq s_i$ 怎么办？我们考虑 $\pi_{\pi_{i-1}}$，令它等于 $j$ 则若 $s_j=s_i$，则 $\pi_i=j+1$，否则继续 $j=\pi_j$。这样循环下去直到求出 $\pi_i$ 或 $j=0$ 结束。若最终 $j=0$ 且 $s_j\neq s_i$ 则 $\pi_i=0$。
vi pi(n);
for(int i=1;i<n;i++){
int j=pi[i-1];
while(j>0&&s[j]!=s[i])j=pi[j-1];
j+=(s[j]==s[i]);
pi[i]=j;
}复杂度证明
- 这里 $j$ 其实可以是一个全局变量，因为每次循环开始
j=pi[i-1]，循环结束pi[i]=j。 - $j$ 只会在
while循环中，根据 $\pi$ 的定义_{j-1}$ 一定小于 $j$，所以每次j=pi[j-1]，$j$ 至少会减 1。 -
j+=(s[j]==s[i]);处增加最多 1，每次循环最多，$p执行一次。因此 $j$ 最多增加 $n-1$。 - $j$ 不能小于 0，所以
while总共至多执行 n-1 次。 - 总复杂度为 $O(n)$。
应用
字串查找
令 $S=t+\#+s$，我们求出 $S$ 的前缀数组 $\pi$，则从 $s$ 在 $S$ 中对应的位置找，若 $\pi_i=|t|$，则 $i$ 对应的在 $s$ 中的位置即其前 $|t|$ 个字符组成就是 $t$。
失配树
我们在算出 $s$ 的前缀数组 $\pi$ 后，将节点 $i$ 与 $\pi_i$ 连接即可得到一颗树，且树根为 $0$。对于每次询问 $x,y$，求出它们的 LCA $f$，若 $f\neq x,f\neq y$ 则答案为 $s[1\dots f]$，否则 $f=\pi_f$，答案为 $s[1\dots f]$。
ACAM
即 AC 自动机，适合叫做 exKMP。主要用于解决如下问题：
KMP 中，我们在一个序列上匹配，失配时就跳到 $\pi_i$。而在有多个模式串时，我们可以在 Trie 树上做匹配，失配时就跳到其失配指针指向的位置。
失配指针
根据上文提出的失配树，我们可以定义出失配指针（fail）：
在 Trie 树上，节点 $u$ 对应一个字符串 $s$。$u$ 的 fail 指针指向树中的另一个节点 $v$，$v$ 对应的字符串是 $s$ 的最长真后缀。
举个例子，现在依次有 3 个模式串 $\texttt{aba},\texttt{b},\texttt{bab}$，则构建出的 Trie 树如下，其中蓝色箭头表示失配指针：
如何求出每个节点的失配指针？
我们按照 BFS 序遍历每个点。当遍历到 $u$ 时，设其父节点为 $f$，$f$ 到 $u$ 的树边对应字符 $c$。$f$ 的失配指针 $fail_f$ 一定已经求出：
- 若 $fail_f$ 存在边为 $c$ 的孩子 $v$，则 $v$ 一定是 $u$ 的失配指针。
- 否则，跳到 $fail_f$ 的失配指针 $fail_{fail_f}$ 处，继续查找，找到为止。
伪代码如下：
int get_fail(int p,char c){
if(tr[p].son[c]!=0)
return tr[p].son[c];
else
return get_fail(tr[p].fail,c);
}不过，这样递归的效率低下。由于递归的状态只有 $p,c$ 两个参数，可以记忆化（直接记录到 $son$ 中即可），并换成非递归写法，得到如下代码：
void build(){
queue<int>q;
for(int v=0;v<26;v++)if(tr[0].son[v])q.ep(tr[0].son[v]);
// 根节点 0 在建好树后就已经初始化好了，无需再处理
// 这里不直接 q.ep(0) 是因为失配指针需要指向真前缀，而不能指向自己
while(!q.empty()){
int p=q.front();q.pop();
for(int v=0;v<26;v++){
int s=tr[p].son[v];
if(s)tr[s].fail=tr[tr[p].fail].son[v],q.ep(s);
else tr[p].son[v]=tr[tr[p].fail].son[v];
}
}
}匹配
接下来该统计答案了，方法也很自然，根据文本串在 Trie 树上遍历一遍，记录每个节点经过的次数。不过要注意，一个节点的经过次数对其 $fail$ 也有贡献，所以要按照逆 BFS 序遍历（可以在 build 时记录这个逆序），算贡献。
完整代码
#include<bits/stdc++.h>
using namespace std;
#define dbg(x) cerr<<#x":"<<(x)<<' '
#define dbe(x) cerr<<#x":"<<(x)<<'\n'
#define eb emplace_back
#define ep emplace
#define endl '\n'
using ll=long long;
using vi=vector<int>;
using vl=vector<ll>;
using tp=tuple<int,int>;
const int LEN=2e5;
struct AC{
struct D{
int s[26];
int fail;
};
vector<D>tr;
AC():tr(1){tr.reserve(LEN+5);}
int makeD(){
tr.eb();
return tr.size()-1;
}
int insert(const string&s){
int p=0;
for(char c:s){
int v=c-'a';
if(!tr[p].s[v])tr[p].s[v]=makeD();
p=tr[p].s[v];
}
return p;
}
vi st;
void build(){
queue<int>q;
for(int v=0;v<26;v++)if(tr[0].s[v])q.ep(tr[0].s[v]);
while(!q.empty()){
int p=q.front();q.pop();
st.eb(p);
for(int v=0;v<26;v++){
int s=tr[p].s[v];
if(s)tr[s].fail=tr[tr[p].fail].s[v],q.ep(s);
else tr[p].s[v]=tr[tr[p].fail].s[v];
}
}
}
vi work(const string&s){
vi a(tr.size());
int p=0;
for(char c:s){
int v=c-'a';
p=tr[p].s[v];
a[p]++;
}
while(!st.empty()){
int u=st.back();st.pop_back();
a[tr[u].fail]+=a[u];
}
return a;
}
};
int main(){
cin.tie(0)->sync_with_stdio(0);
int n;
cin>>n;
AC ac;
vi p(n);
for(int i=0;i<n;i++){
string s;cin>>s;
p[i]=ac.insert(s);
}
ac.build();
string s;cin>>s;
auto a=ac.work(s);
for(int v:p)cout<<a[v]<<endl;
return 0;
}