后缀数组及其建图
目录
第二次学了…感觉像是重头来过一样…
参考资料
后缀自动机学习笔记-by Menci
校内PPT
概念
-
后缀自动机实际上是两个东西的合成物：一个有向无环图（转移）+一个后缀链接树。并且后缀自动机最初始拥有一个根，暂且让我们把它称作Start；
-
终点位置（endpos），就是一个字符串的右端点，即结束位置；
-
终点集合：母串中的一个子串肯定有可能在母串中不止出现了一次，例如ababab中的ab就出现了3次，那么每一次出现的终点位置组成的集合就是这个子串的终点集合。
-
终点等价类：拥有相同的终点集合的子串就被称作终点等价类。例如abcde,bcde,cde,de,e,它们在abcdeabcde这个母串中就属于同一个终点等价类。
-
后缀自动机的第一部分（有向无环图），边代表字母（叫做转移边），点代表一个终点等价类（而不是一个某一个特定的串）；第二部分（后缀链接树），边代表后缀链接，点的定义不变。两个部分共享同一个点集。
-
在一个终点等价类（一个节点）里面，我们还有两个值，一个叫做minlen，是这个等价类代表的最小的子串；还有一个叫maxlen，是这个等价类代表的最大的子串。
-
后缀链接：后缀自动机中的每一个点（除了Start之外），都有这样子的一个链接，其含义是将一个终点等价类分成很多个部分。假设当前的一个子串是abcde，有一个点是p，可能p只代表了abcde,bcde，而p的后缀链接指向的点pre[p]（等价类）代表的可能就是cde,de，再往上还有一个点pre[pre[p]]代表着e，但是p只会连向pre[p]，也就是maxlen[pre[p]]=minlen[p]-1的那个点。注意，Start代表着空串。也是所有串的后缀，属于任意一个终点等价类。
（如有疏忽，后面会做详细的解释）
引理
一. 对于两个非空子串str1,str2而言，如果strlen(str1)<=strlen(str2)并且str1和str2处于同一个终点等价类，那么str1必定是str2的后缀。
证明：因为两个串属于同一个终点等价类，那么它们右端点在母串中的任意一个位置一定是重合的。所以说str1一定是str2的后缀（几乎可以由定义直接得到）。
二. 对于两个非空子串str1,str2,如果满足strlen(str1)<=strlen(str2)，他们所代表的的终点集合要么交集为空，要么Set(str2)属于Set(str1)。
证明：分两种情况讨论。
一种是str1是str2的后缀，那么出现了str2的地方就一定出现了str1，但是出现了str1的地方不一定出现了str2，那么根据终点集合的定义就能发现Set(str2) 属于Set(str1)；
还有一种情况，就是str1不是str2的后缀，那么出现了str1的地方不可能出现str2，那么交集就为空了。
三.在一个终点等价类里面，将其代表的串排序后，一定呈现：前一个串时候一个串的后缀，并且前一个串的长度正好是后一个串的长度-1。
证明：假设有一个终点等价类，里面最长的串是abcde，那么这个等价类里面必定还有bcde,cde,de,e，正好符合（又是由定义直接可得？？）。
四.后缀链接形成了一棵以Start为根的一棵树
证明：假设有一个节点p，因为它的后缀链接只会连向比maxlen自己的minlen小1的那个点，那么就有了唯一的一条后缀链接。这样每一个点都有唯一的后缀链接，而Start没有后缀链接，那肯定就是一棵树。
五：沿着后缀链接向上跑的过程，可以看做是将终点等价类进行不断地合并，越往上走，能够代表的终点等价类越完整
证明：由引理三的证明可以感受一下，越往下面的点，它代表的终点等价类的部分的子串数越来越少；而沿着后缀链接向上走的过程中，由于长度越来越短，所以说它能够代表的后缀等价类也越来越多。
举个例子：母串为abcdeabcde，其中代表eabcde那个点只有这一个子串，也只能够代表这一个子串；而包含e能够代表e,de,cde,bcde,abcde,eabcde…，能够代表的终点等价类的范围显然就宽了不少，也就是将下面的那些子串合并起来了。
到底如何构造
说道底，这才是后缀自动机真正的难点所在…我甚至建议一边看建图过程一边看引理的证明。过程主要注重理解。
在这里采用的是动态的加入过程，也就是一个字符一个字符地加入。
假设当前加入的字符是chr，然后让我们再来定义一些奇奇怪怪的变量：
- 当前新建的点是np。
- 上一次加入的点是p，也就是这次我们需要把np接在后面的那个点。同时p也是我们通过后缀链接不断地向前跳的当前点。
- 假设遇到p有一条字符chr的转移边，那么就令q为p->nxt[chr]。
- 如果要新建关于q的新建点的话，我们就叫它nq吧。
有了这些之后，让我们来看一下怎样建立后缀自动机。注意，后缀自动机的两部分都要兼顾哦。（后面的图中，虚边都表示转移边，实边都表示后缀链接）
Step1:
当前要加入的字符为chr。首先申请一个新的节点np，然后利用全局维护的上一次插入的新节点last，令p=last(根据之前的定义)，然后又因为你新加入这个节点代表的最长的子串(也就是maxlen)就等于last的maxlen+1，即令maxlen[np]=maxlen[last+1]（附加一句，其实在过程中我们只需要维护maxlen，minlen只是用来帮助我们进行分析的）。
Step2:
然后现在我们就有了新的节点np和当前位置p。我们沿着p的后缀链接往前跳，每走到一个点p，就需要判断当前的p是否有字符chr这条转移边。如果没有，就进行以下的操作：
在p点新添加一条chr的转移边，连向np。因为p点没有一条到达chr的转移边，那么在p处添加一个字符后可能就出现了以前没有的串，所以需要新加入一条转移边。
新加入转移边后，就可以让p继续沿着后缀链接往前跑，每次继续进行这样的判断就可以了。
(因为当前的p可能只代表了某个终点等价类的某一个长度区间，而为了能够表示所有的子串，我们需要将以chr结尾的这个终点等价类的所有的子串都表示出来，多以需要往前跑)。
需要注意的一点是，假如说一直都没有遇到一个点有chr这条转移边，那么我们就需要将np的后缀链接指向Start。因为这个时候有maxlen[Start]=minlen[Start]-1，根据之前后缀链接的定义可得，此时必须，也只能将np的后缀链接指向Start。
如上图，就是这样跑（一直都没有chr这条转移边时）建出来的图的样子了。
Step3
到了这里，终于来到后缀自动机真正有意思的地方了，也是最复杂的地方。
我们前面说了没有chr这条转移边的情况应该如何处理，那有chr这条转移边又该怎样呢？
先上个图：
当前的p点就是这样一种情况（其中的chr边是本来就有的）。q是p本来的chr边转移到的点。
然后我们需要分两种情况进行讨论。
其一是maxlen[p]+1=maxlen[q]。这个时候说明了q所代表的的最长的子串是由p加上chr之后转移过来的，这个时候就可以直接让np的后缀链接接到q上，然后直接退出就可以了（因为此时的q应该已经代表了它应该代表的完整的终点等价类）。也可以由公式算出：
\(maxlen[q]=maxlen[p]+1\)。设p之前在的那个点是p’，又因为\(minlen[p’]=minlen[u]-1\)且\(maxlen[p]=minlen[p’]-1\)。然后通过公式的代换，就能够得到\(maxlen[q]=minlen[p’]-1+1=minlen[u]-1\)，再根据后缀链接的定义就应该连这条边作为后缀链接了。
其二是maxlen[p]+1<maxlen[q]，这个时候就不能够直接让np的后缀链接直接接到q上了，因为q此时不一定只代表了maxlen[p]+1的部分，还代表了>maxlen[p]+1的部分，而这一部分是不能够被算进去的。这个时候应当怎么办呢？
此时我们需要新建一个节点，将q中>maxlen[p]+1的那些子串分离出来。
可以看出新加了不少的边。
让我们先从实边，也就是后缀链接说起。因为nq代表的是maxlen[nq]=maxlen[p]+1的部分，而q代表的是maxlen[q]>maxlen[p]+1的部分，而minlen[q]=maxlen[nq]+1，所以说q必定要将后缀链接指向nq。而np的后缀链接必定也要连向nq。同时，由于可以将nq和q看做是一个整体，所以说nq应继承q原来的信息，将后缀链接之前原来的q的后缀链接指向的那个点。
在来看转移边。p的后缀链接以上的点如果有连向q的转移边，也要重定向到nq。唯一不同的是t,是之前令maxlen[t]+1=maxlen[q]>maxlen[p]+1的那个点，它仍然需要将转移边指向q，因为此时上式仍然成立。而p的转移边应指向nq，因为此时我们设的就是maxlen[nq]=maxlen[p]+1。
这样子就成功应对了这种情况。同样也可以直接退出了。
先更到这里，有一些经典运用的话，后面会补上。板子也会贴在后面的~~