SAM构成

用最少的状态存一个字符串的所有后缀状态

对于$S=aabbabd$的后缀自动机



发现所有的后缀都能从根节点的一条路线遍历出来

发现此时节点最少。

所有的子串都能在上面表示出来，且不是子串不存在。

绿色虚线是$Link$,一个转移工具。

SAM的状态集

子串结束位置集合叫$endpos$

一个子串$s$,$endpos(s)$指的是$s$在$S$所有的出现结束位置集合

$S=aabbabd$,$endpos(ab)={3,6}$结束位置是$3,6$

把所有子串的$endpos$求出来，如果两个子串的$endpos$ 相同，就是一个等价类，可以在个点上表示出来，按长度排序，最终这些$endpos$的每一类相连构成了$SAM$,且在$SAM$上用边连接。


性质


$1.s1$是$s2$子串


显然$endpos(s2)$是$endpos(s1)$子集

$2.$由上面性质得知,$endpos$相同的点必然为子串关系，那么必然长度连续

$3.$最长的定义为$longest$,最短的定义为$shortest$

$4.$长度在$longest$和$shortest,$必然是子串关系

后缀链接

$substring(st)$包含$longest(st)$的一系列连续后缀，但是会断掉$???$

显然越小出现的地点越多，那么连续一段之后就出现了新的状态

对于一个长串在每个后缀子串转换状态时之间进行连边的工具就是$Link$

转移函数

感觉类似$AC$自动机里的边，可以走到每个字符串

对于一个状态$st$考虑它在自动机上下一个状态是什么

将下一个状态叫做$next(st)$，就是当前状态的所有结尾位置$+1$的字符

转移函数的性质

$1.$对于一个$st$和$next(st)$中的字符$c$

这个东西的转移函数就是加一个新字符不变的位置搞到一起，然后分成几部分

相当于大区间加一个新字符形成的新区间$ed$，就是找到一个包含变化后$st$的集合

相当于在加边(字符$c$)后得到的新集合

构造SAM

增量法

需要 $maxlen,minlen,trans,Link$辅助构造

考虑从开始逐渐加入字符，构造识别每个前缀的自动机

加入新字符，会多$i+1$个子串需要识别，需要添加状态，使其包含这些子串

如果此时所有$Link$上的所有状态$v$，所有的$trans$都等于$NULL$，相当于没有这个转移边，那么直接改trans

这时候停一下，$SAM$其实是各个状态之间的相互连接罢了

我貌似回忆出来了

$trans$指的是加上一个新的字符之后会到达那些状态

$Link$指的是一个字符串后缀在变化后状态会进行哪些变化

$1.$此时$Link$链上的所有$trans[x][s[i+1]]$全为$NULL$,则表示全部状态没有出现过转移到该状态，那么有了这个字符之后，就能从这些状态转移过来，那么这些串的$trans$就可以指向这个状态

$2.$还有一种情况，有一个节点$trans!=NULL$,

然后改。。。

我去瞅代码去了