$SAM$学过一段时间了，本来想写一点总结的，结果一直咕咕咕咕咕咕咕咕咕到了现在……
概念和构造
-
关于$right$集合
$right$集合是指结束位置相同的一堆子串结束位置形成的集合，像字符串$aabaaabba$，子串$aab,ab$是$right$集合相同的，因为它们的结束位置都是${3,7}$（从$1$开始标号）
$right$集合相同的两个子串，短子串肯定是长子串的后缀，这个由上面的定义可以轻松得出
依据这个，可以得到结论：（用$right_s$表示子串$s$的$right$集合）
子串$a$是子串$b$的后缀，那么$right_b\subset right a$，即$right_b$是$right_a$的子集
随着子串不断变长（向前加），它所在的位置集合大小不会变大
如果子串集合${a_1,a_2,…,a_n}$的$right$集合相同，那么它们的长度连续
由上一条可以轻松得出此结论
设最长串长度为$lmax$，最短串长度为$lmin$，则这个$right$集合的$lmin-1$一定是下一个$right$集合（指后缀中的下一个）的$lmax$，这里下面说$Parent$树的时候会详细介绍
所以只要知道子串$a$所属的$right$集合和长度就能确定$a$了
-
关于转移
如果$right$集合相等的某些子串后面加上字符$c$，那么它们形成的字符串的$right$集合也相等（不一定是原来的），所以转移$son_{s,c}$表示在一个状态（指$right$集合相等的某些子串）后面加上一个字符$c$后能到达的状态
感觉用到的不多
-
关于$Parent$树
刚才介绍$right$集合最后提了一嘴集合中最长子串长度$lmax$和最短长度$lmin$的关系，现在详细介绍一下
设$right_a$中最短子串为$s$，如果$s$再继续减少字符（指形成更短的后缀），它的结束位置集合肯定就不再是$right_a$了，设它现在的位置集合$right_b$，那么它现在就是$lmax_b$（即$right_b$中的最长子串），有$lmax_b=lmin_a-1$
那么代表$right_a$（结束位置集合是$right_a$的子串集合，以后都这么叫了一个一个打烦死）的节点在$Parent$树上的父亲就是代表$right_b$的节点
这里也有$right_a\subset right_b$
如果有$son_{s,c}$存在，那么$son_{Parent_s,c}$也一定存在
-
关于构造
$SAM$是在线构造的，依次把字符串$a$的每个字符往里面塞
发现如果只有代表$right$集合的节点会构造乱的，所以要往里面添一些“其他节点”（“其他节点”依然维护信息）
哎呀讲构造真是烦死
现在要加入一个字符$c$，设前面加入字符形成的字符串为$S$，这里肯定形成了新的$right$集合，$S$的状态$a$能通过加$c$转移到新状态$b$，有$son_{a,c}=b$
上面说了
如果有$son_{s,c}$存在，那么$son_{Parent_s,c}$也一定存在
所以还要依次更新它在$Parent$树上的祖先
一路往上跳，如果祖先$u$没有这个转移，直接塞上这个转移就完事了
跳跳跳到根了！恭喜你没有遇到冲突，成功添加了一个点
跳跳跳到$u$，但是$v=son_{u,c}$已经存在了，这时候如果有$lmax_v=lmax_u+1$，说明$S$加上$c$也能转移到$v$，$v$的$right$集合更大，所以$v$为$b$在$Parent$树上的父亲
这时候如果有$lmax_v>lmax_u+1$，这时候不能强插（具体原因不说了烦死），于是再新建一个节点$v’$，有$lmax_{v’}=lmax_u+1$，这里相当于两个状态，$S$加$c$后缀对应状态和$lmax_u+1$对应的状态，前面状态对应串较长，对应子串较少，所以$Parent_v=Parent_b=v’$，再把祖先的$v$都替换成$v’$
差不多这个意思吧背过板子就行了
一些常用操作
-
求$right$集合大小
$x$的$right$大小就是$Parent$树上子树和，注意“其他节点”不计入贡献
-
求本质不同的子串个数
本质相同的子串肯定属于一个$right$并且长度相等，所以答案就是$\sum lmax-lmin+1$
-
求两个子串的$LCS$（最长公共后缀）
可以发现两个子串的$LCS$的长度就是$Parent$树上代表它们的节点的$LCA$的$lmax$，因为$LCA$及其祖先$right$集合肯定都包含这两个子串的结束位置，且深度越浅代表的子串越短，集合越大
-
求两个串的$LCS$（最长公共子串）
对一个串建$SAM$，然后用另一个串在上面跑就行了，如果当前位置不能匹配，就跳$Parent$，当前节点的祖先肯定包含此位置，找到第一个能往下匹配的祖先继续就行了，注意要维护当前匹配长度和匹配最大长度
-
求第$k$大/小子串
记录$right$集合大小的前缀和，然后就像二叉树找第$k$大一样做了，只不过转成了26多叉树
$k$小同理
-
求多个串的$LCS$（最长公共子串）
对一个串建立后缀自动机，然后别的串在上面跑，每个串记录每个位置能往前匹配的最大值，对于一个位置每个串的能匹配最大长度就是每个串在这个位置的值取$min$，最后所有位置取个$max$就好了
还有啥其他玩意想起来再补咕咕咕预警
关于与线段树合并结合
$SAM$和线段树合并结合乱搞是常见套路
用线段树能干些什么？
加入一个点的时候，在当前点的线段树里标记一下加入位置，线段树合并从叶子合并到根的过程中每个节点的$right$集合具体位置就能表示出来了
然后就可以判断一段子串是否属于某个区间了
去做几道题体会一下吧
关于与其他乱七八糟的东西结合
因为$Parent$关系构成了一棵树，所以所有树的算法数据结构都可以往上套……
与其他的啥玩意套也挺常见的……
放下题单，就这样吧
