这只是个人小结，没啥大意义。

后缀数组

其实就是通过把字符串的所有后缀排序来实现一些东西。

后缀排序可以用倍增+双关键字来实现。

然后排完之后可以求出height数组，然后就可以用RMQ求LCA了。

后缀自动机

各种复杂度都是线性的，非常优秀。

原理：把具有相同right集合的状态缩成一个点，这个点内的所有状态互为后缀。

每个状态有一个minlen和maxlen，表示这个状态内的最长子串和最短子串。

构造方法：增量构造法，考虑这个字符的加入会使之前的所有后缀增加一个字符，所以可以通过调fail树来构造。

然后就是father的问题，如果l[p]+1=l[q]那么可以直接连father，否则直接连状态会出现问题，那么我们就新建立一个节点。

应用：

1、求某个子串在原串中的出现次数，在后缀节点上大标记，该子串代表的节点子树的size就是出现次数。