后缀树
后缀插到trie树里。 把许多节点压到一起。节点数量是O(n)的 节点可以记录原串的起始终止位置。 可以查询子串。
性质： LCA深度为LCP长度 某个点的子树叶子个数为点所代表的子串的出现次数。 按字典序dfs就是后缀排序结果。
后缀数组
求法：倍增，基于基数排序 对于SA LCP(i,j)=min(hei[i]) 可以枚举一个k，去掉hei<k的，把SA数组根据Hei分成一些块。 块内的两两之间LCP的长度都大于等于k k可以枚举，或者二分。
后缀自动机
核心： 1.Right集合 2.Parent树的联系 3
学习思考： 后缀树 反串上建SAM的Parent树就是后缀树。 trie树建后缀自动机
**求两个串本质不同的公共子串个数
#号连接，然后跑后缀数组
SA序列，记录所属的字符串s1，或者s2
排列成形如：
s1
s2
s2
s1
s2
s1
...
新出现的公共子串一定是s1,s2之间的height（例如s1,s2后s2,s1）
然后考虑再次出现的时候去掉之前出现过的。
发现就是之前上一次s1,s2的LCP位置取min过来的长度，减去即可。