一.模板复习
1.SA
倍增排序，每次排序，以前半个串为第一关键字，后半个串为第二关键字排序，排序可以用基数排序，复杂度O(nlogn)

一些比较适合在SA上做的题目:
1.LCP长度有关
2.一个经典套路：SA上按height启发式合并，例题：1.shopee杯武大校赛2019正赛C题 2.洛谷“小W与数列”
通常用来维护和LCP有关的最小化/最大化题目。

2.SAM
https://www.cnblogs.com/zjp-shadow/p/9218214.html#autoid-4-1-0
这位大佬已经讲得非常非常清楚了，无需我再啰嗦。
PS：本质不同子串个数不需要dp，直接求\(\sum (maxlen_i-maxlen_{fa_{i}})\)，这个是可以在线维护的。
拓展：广义SAM。
构建多串trie，用bfs序加入后缀自动机。