对于后缀结点和失配指针两种说法，本文采用后缀(Next)结点这种说法。
这里说的后缀树，并不是真正的所谓的后缀树。只是后缀树的一种，或者说，是一种广义的后缀树。
见：https://yhf4aspe.github.io/2018/03/17/AC%E8%87%AA%E5%8A%A8%E6%9C%BA/
前缀后缀什么的不要晕啊！要有耐心去分析！
Trie树，就是前缀树。
前缀的后缀是匹配。
我们用AC机解决后缀，构造出后缀树。
用一道例题引入以下
给出几个模式串（一个字典）比如：A、AB
定义一个字符串S的得分：模式串在S中出现的次数。比如：ABAB的分数为4
构造一个长度为L的字符串使得分最高，输出最高得分。
S的得分可以理解成这样，枚举S的前缀si，再用si的后缀与模式串匹配（抽象吧，其实就是枚举匹配的结束点）。这样的话得分就可以用一个递推来表达了。
f_S=sum(f_si); f_i=f_(i-1)+f_si; f_S=f_len （其中f_si的求就是在AC机上查询一趟）
然而，题目要求的是构造，这可能会对我们造成很大疑惑，但是理解了如何得分，会对我们用DP解决此题有很大帮助。
先想到一维，也就是枚举前缀si，当然只有一维是不够的，我们还需要能求出f_si的一些信息，所以状态大概是这样的
f[i][x]，其中x表示一个字符串，可以通过f[i-1][y]推得，其中x=y+X，也就是在y的后面再加了一个字符。
这样我们的转移方程就出来了，f[i][y+ch]=f[i-1][y]
这就得到了最原始的DP，但我们发现，记录x的代价是很高的，所以要优化，我们可以发现，有些字符串是不用记录的，并不会作为状态。
那么是怎样的字符串才会作为状态呢？即为：能对当前或以后做贡献的字符串才保留。也就是，能使当前的得分增加或将来能的字符串。
仔细想想，也就是每个模式串的前缀，也就是枚举Tire树上的每个结点。
所以方程就优化成了这样f[i]jf[i][p->ch]=f[i-1][p]+Query(p,ch)大概是这样的。
我们可以先预处理Query(p,ch)这样就可以，在O(len×size)的时间解决。
这大概是AC自动机对DP优化的思路，能对当前或以后做贡献的字符串才保留，而这些字符串也就是Tire树上的每个结点。
总的来说，用Tire缩小状态，用AC自动机快速查询。
就是在跑过AC机的Trie树上，用求出的Next结点构成的新树（因为只有一条出边，所以是一棵树）。
毕竟AC自动机就是一个求Next的算法，那么我们把构成的这棵树研究透彻了，会对AC机的应用大有帮助。
这是一棵Trie树和用其构造出的Next树：
可能有点简单，可以自己画一个更大的去理解。
这棵树有什么性质呢？其实只需根据Next结点的定义。可以得出这么个结论：
在Next树上，u是v的父亲（祖先），那么st_u是st_v的后缀
其实这个Next树，就是一个后缀树。
安利一个构Next树的模板
void Bfs(int rt)
{
op[0]=rt; de[rt]=1; ac[rt].nx=rt; CSH();
for (int Head=0,Tail=1; Head<Tail; Head++)
{
int u=op[Head];
for (int ch=0; ch<MLson; ch++)
{
int v=ac[u].son[ch];
if (v==-1) continue;
de[v]=de[u]+1; op[Tail++]=v;
int &p=ac[v].nx;
if (de[v]<3) p=rt;
else
{
for (p=ac[u].nx; p!=rt; p=ac[p].nx)
if (ac[p].son[ch]!=-1) break;
if (ac[p].son[ch]!=-1) p=ac[p].son[ch];
}
Ins(p,v);
}
}
}
## AC自动机与树综合
在一棵Tire树上，询问树上结点x,y，问字符串x在字符串y出现的次数（树上的点可表示一个串）。询问离线。
根据Next树的定义，在Next树上，只要是x子树的点，x都是他们的后缀，而这些点恰好又在root->y这条路径上，这就是x在y中出现的次数了。
所以对于每个询问，就变成了统计点的个数，使该点在Next树上，是x的子树，在Tire树上，在root->y的路径上。
先解决子树问题，我们可以用常用的手段，在Next树搞个dfs序，满足时间戳在某个范围内就是在子树上了，这里不做详细说明。
链的问题不好解决，在此有两种方法。
一、易想，但难编。
直接剖分Tire树，把链割成logn个连续段，然后问题就变成了这样一个问题，问一个点同时满足在两个区间内的个数，也就是一个经典的矩形取点问题，可以直接上树套树，扫描线，主席树等等数据结构维护，推荐扫描线，又好写又快，总复杂度mlognlogn
二、难想，但好写，
把询问离线，dfs遍历Tire树，这样路径的信息就能保留。我们每搜索到一个点，或回溯回去，就把该点对应在Next树上的标记为1（出现过）或0（没出现过），这样问题就变成子树求和的问题，一个支持单点修改，区间查询的数据结构就够用了，其中树状数组最好写了。总复杂度mlogn
n是树的大小。
CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：AC自动机的运用”