SAM整理

SAM整理

by AmanoKumiko

1.基本概念

? 表示后缀的位置（终止状态）：从整个\(SAM\)的状态开始一直跳\(link\)

? 表示前缀的位置（终点）：插入一个点后的状态

? 表示\(endpos\)相同的串：一个状态

? 表示子串：路径

2.子串

? 一个状态\(x\)的子串个数：\(len(x)-len(link_x)\)

? 一个状态\(x\)的子串总长度：\(\frac{(len(x)+1)len(x)-(len(link_x)+1)len(link_x)}{2}\)

? \(LCS\)：不断通过转移和\(link\)找出\(A\)串的每个前缀和\(B\)串的最长公共后缀

? 第\(k\)大子串：求出路径数（子串数）后贪心即可

3.出现

? 出现次数在每个前缀位置标记，对树上子树中的标记求和

? 是否出现：直接放进去遍历转移即可

? 第一次出现：树上子树中的最小终点

? 所有出现位置：树上子树中的所有终点

4.广义\(SAM\)

? 建\(Trie\)，\(bfs\)，每次在其祖先的终点进行\(extend\)操作