主讲一些自动机相关、高级技巧相关。
Part 1 AC 自动机
是最好理解的一个自动机捏。
Part 1.1 性质与探索方向
AC 自动机本身基于 Trie，即去掉后面说的 fail 指针，它就是一棵 Trie。
在此之前我们需要了解它的作用：把多个模式串插入自动机进行匹配。也就是说，相比于 KMP，我们对于主串的考虑延伸到了多个模式串上的匹配情况。
不妨先尝试一下用 Trie 去匹配主串 \(S\)。
假设考虑到了第 \(i\) 个字符，即 \(S_i\)，想要找出以 \(i\) 结尾能与模式串集合中的哪些串匹配上。那么，一个模式串能匹配上，必然是 \(S[1,i]\) 的后缀。对应在 Trie 树上自然是根到一个节点形成的链上的所有字符串。
也就是说，我们只要能找到这个匹配的节点的深度最大者（此时为最长匹配后缀），就可以是一个匹配串。
那么，如何找到短一些的匹配后缀？如何快速找到这个节点？这里我们就要引入可爱的 fail 指针。
Part 1.2 fail 指针
如果我们发现，abcab 是当前字符结尾的后缀的最长匹配串，那么还有什么串可能成为短一些的匹配串呢？
相信你已经发现了，这个串肯定是最长匹配串的后缀（废话）。如果能找到长度仅次于它的匹配串，我们貌似可以建立一个树形结构？
对于每一个节点 \(V\)，定义其对应的匹配串为 \(S_V\)。若存在一个最长串 \(T\) 为 \(S_V\) 后缀，\(T\) 的对应节点为 \(U\)，我们定义 \(V\) 的 fail 指针 指向 \(U\)。
没错，顺着 fail 指针形成的树链往上爬，你就可以找到当前后缀能匹配的所有串啦！
可是接下来，我们还有两个问题。
- 如何求 fail 指针？
解：递推求解。若节点 \(V\) 的父亲为 \(U\)，找到 \(U\) 的 fail 指针对应节点 \(U'\)，在 \(U'\) 的儿子中寻找 \(V\) 节点对应的字符。若存在，即为 \(V\) 的 fail 指针；否则，我们继续跳链，寻找 \(U''\)……以此类推。
复杂度寄了，跳链过程是可以通过记录省略。
解 2（优化）：对于一个节点 \(U\)，若其不存在对应字符 \(c\) 的儿子，则令其儿子为其 fail 指针的对应儿子。即省略跳链过程，上面的过程中即使 fail 指针没找到对应儿子，也直接用存的值。
（大家可以仔细琢磨这个过程：如果找到即为所求，没找到，我也是沿用的上一层的 fail 的答案，上一层的 fail 没找到，仍然沿用父亲）
- 如何快速找到当前后缀的最长匹配串的对应节点？
相似的过程，利用上一个字符的匹配情况，跳 fail 指针。同样利用技巧省略枚举过程。
那么，多模式串的匹配问题被我们在线性复杂度内解决了。
当前后缀能匹配的所有模式串都在 fail 树上其匹配节点到根的路径上的所有串。
Part 1.3 例题
1. P3803
本题并不是最纯正的模版。
套用我们刚才的做法，但是有一点需要注意：多次出现的模式串只算一个。
这可怎么办？我们发现，由于每次都能匹配一个前缀，这貌似是要我们每次覆盖一条到根的路径，最后求一遍覆盖的点权值之和。
难道要 DS？不，我们可以暴力跳链并标记，跳到一个被标记过的地方，就可以不跳了。有人到过这里，那么再往上肯定都给算了。每个点都只会被我们标记一次，复杂度得以保证。是一个优雅的暴力呢。
ll n; string str[1000005],S;
struct Trie{
ll son[26], cnt, fail;
}trie[1000005];
ll dfn=1;
void update(string S){
ll sz=S.size(), root=1;
for(ll i=0;i<sz;i++){
ll now=S[i]-'a';
if(!trie[root].son[now]) trie[root].son[now]=(++dfn);
root=trie[root].son[now];
}
trie[root].cnt++;
}
void getFail(){
for(ll i=0;i<=25;i++) trie[0].son[i]=1;
queue<ll>Q; Q.push(1);
while(!Q.empty()){
ll x=Q.front(); Q.pop();
for(ll i=0;i<=25;i++){
ll tmp=trie[x].son[i], fafail = trie[x].fail;
if(!tmp){
trie[x].son[i] = trie[fafail].son[i];
}else{
trie[tmp].fail = trie[fafail].son[i];
Q.push(tmp);
}
}
}
}
ll query(string S){
ll sz=S.size();
ll root=1, ans=0;
for(ll i=0;i<sz;i++){
ll now=S[i]-'a';
ll k=trie[root].son[now];
while(k>1 && trie[k].cnt!=-1){
ans+=trie[k].cnt;
trie[k].cnt=-1;
k=trie[k].fail;
}
root = trie[root].son[now];
}
return ans;
}
void solve(){
cin>>n;
for(ll i=1;i<=n;i++) cin>>str[i], update(str[i]);
getFail();
string S; cin>>S;
cout<<query(S)<<endl;
}