[学习笔记]后缀系列总结

后缀树

后缀插到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过来的长度，减去即可。

[学习笔记]后缀系列总结

原文：https://www.cnblogs.com/Miracevin/p/10105555.html