后缀自动机
这两个星期都在学后缀自动机，然后感觉很玄乎。照惯例写一篇东西加深一下印象。
后缀自动机是啥？
有向图
我看了看，貌似很多人的博客在后缀自动机的定义里都提到了这个东西
然而能学后缀自动机的早就应该理解了吧
节点与边
既然后缀自动机是个有向图，那么其中肯定有一些节点和边（理所当然）
每个边都代表一个字符，一些从根到最后一个节点的边所形成的链就是一个后缀
每个点都是以根到这个节点的所有的链存储着一些后缀的集合，且这些后缀互为后缀关系
可能有点难懂，大概就是下面这张图：
然后大家看到除了黑色的边以外还有一些蓝色的边，指向的是那些节点的上一个可接受状态
上一个可接受状态意味着，以这个节点结束的后缀，也是我们当前节点的合法后缀
总结：后缀自动机就是一个有向图，由字符的后缀组成
后缀自动机的构造过程
我们从代码入手可能会易于理解一些（？）
先看看几个变量的定义：
char s[2000001];//输入用的字符数组int last,cnt;//last是上一个的节点编号，cnt是当前节点编号int ch[4000001][26];//儿子，和trie是一样的，一条边就是一个字符int fa[4000001];//前面解释过的，指向上一个可接受节点int len[4000001];//每个节点所代表的后缀的最长的长度
核心代码如下，四个重点后面会慢慢讲的
void ins(int c){ int p=last,np=++cnt;//np是新节点，p是上一个节点 last=np; len[np]=len[p]+1;//最长的后缀是上一个节点+1 //第一个重点来了 for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;//当p依旧存在，且这个节点暂时还没有一条出边代表这个节点时， //不断沿着fa往前跳，设置一个新的后缀 //第二个重点 if(!p)fa[np]=1;//把自己的最短后缀设置一下。假如我已经跳到了代表根的那个节点， //就是说没有一个节点已经包含我要插入的后缀的话，我们把fa[np]直接指向根节点 //也就是说，出现了一个新的后缀，就是我刚插入的这个字符构成的 else { //第三个重点 int q=ch[p][c];//与上一种情况相反，我们在往回跳的途中发现已经有一个和现在插入的这个相同的后缀了 if(len[p]+1==len[q])fa[np]=q;//假如这个q所代表的最长的后缀的长度为p的最长后缀的长度+1 //也就是说，已经存在一段连续的后缀与新插入的后缀相等了，那我们就把fa指向这个节点 else { //第四个重点 //这个玩意儿是因为len[p]+1!=len[q]而做的，也就是说前面有一个后缀满足与当前的后缀一样 //但是这个后缀并不是一个连续的后缀。所以不能直接把fa指向q。 int nq=++cnt;//再新建一个节点 len[nq]=len[p]+1;//这个节点是一个辅助节点，和新建的p是同一个位置的 //这样新建节点的原因是，我们需要把原来那个节点的信息都拷贝过来以形成一个连续的后缀 memcpy(ch[nq],ch[q],sizeof(ch[q]));//把q的儿子都拷贝过来 fa[nq]=fa[q];//nq的fa指向q fa[q]=fa[np]=nq;//然后把原本的q和新节点的fa都指向nq for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq;//一样的拷贝 } }} 现在来详细解释一下上面的几个重点。
重点1
for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;//当p依旧存在，且这个节点暂时还没有一条出边代表这个节点时， //不断沿着fa往前跳，设置一个新的后缀
看图看图：（图中有误，并无黄色节点，但是大家应该都知道last是哪一个吧）
重点2
if(!p)fa[np]=1;//把自己的最短后缀设置一下。假如我已经跳到了代表根的那个节点， //就是说没有一个节点已经包含我要插入的后缀的话，我们把fa[np]直接指向根节点 //也就是说，出现了一个新的后缀，就是我刚插入的这个字符构成的
看图：
补充：假如你还经过中间的节点，你会发现可能会出现一些不合法的后缀，比如你从根走到a，然后略过中间的b走到了下一个节点，这肯定是非法的
重点3
else {//第三个重点 int q=ch[p][c];//与上一种情况相反，我们在往回跳的途中发现已经有一个和现在插入的这个相同的后缀了 if(len[p]+1==len[q])fa[np]=q;//假如这个q所代表的最长的后缀的长度为p的最长后缀的长度+1 //也就是说，已经存在一段连续的后缀与新插入的后缀相等了，那我们就把fa指向这个节点 现在问题来了，上面那一种情况讲的是假如!p，那么我们怎么办
这种情况讲的是假如是ch[p][c]已经存在，我们怎么办
一样的，看图：
重点4
else { //第四个重点 //这个玩意儿是因为len[p]+1!=len[q]而做的，也就是说前面有一个后缀满足与当前的后缀一样 //但是这个后缀并不是一个连续的后缀。所以不能直接把fa指向q。 int nq=++cnt;//再新建一个节点 len[nq]=len[p]+1;//这个节点是一个辅助节点，和新建的p是同一个位置的 //这样新建节点的原因是，我们需要把原来那个节点的信息都拷贝过来以形成一个连续的后缀 memcpy(ch[nq],ch[q],sizeof(ch[q]));//把q的儿子都拷贝过来 fa[nq]=fa[q];//nq的fa指向q fa[q]=fa[np]=nq;//然后把原本的q和新节点的fa都指向nq for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq;//一样的拷贝 } 其实看完上面的那个就会有人有疑问，假如len[p]+1!=len[q]，也就是说，这两个节点不是连续的，
虽然存在这个后缀但是中间还有其他的后缀，那该怎么办？
这个重点4就是为了这个而生的。
上图：
这样建立一个新节点的想法其实蛮暴力的。。。没有我想要的节点，我就自己造一个
时间&空间复杂度
时间是\(O(n log k)\) ，其中k是字符集大小（一般为26），也就是说基本可以忽略不计
空间则是\(O(n)\)的
证明我就真的不会啦
总结
反正后缀自动机就是一个非常棒的东西，可以做很多后缀数组做不到的东西
接下来就是一些有关于后缀自动机的应用了。
后缀自动机的应用
洛谷 P3804 【模板】后缀自动机
咕咕咕。先咕着，回家再做