在学完 SAM 后的三周,某场CF的E题,结果忘了 SAM 的写法…
本文忽略了复杂度证明,在 OI wiki 上证明的很详细了,这里为对 SAM 的原理的介绍。
SAM 对一个字符串(或多个)的所有子串进行高度压缩,使得 SAM 可以在时间复杂度O(n),空间复杂度O(n)被构造出来。确切的说,一个 SAM 最多有 2n−1个节点,3n−4个边。
初识
一个字符串 s 的后缀自动机是一个接受所有后缀的最小有限状态自动机。
例如,对于字符串"abcab"构建的SAM如下,1为起始节点(右图为parent tree):

定义
在构造 SAM 前,先引入几个重要的定义。
结束位置 endpos
字符串 s 的非空子串 t 的 $\operatorname{endpos}(t) $为 t 在 s 中所有出现的位置(以 0 开始计)。
例如对于字符串"abcabbc",endpos("bc")=2,6
若两个子串的 endpos 相等,则称这两个子串为同一个 等价类
。也就是说,一个字符串有若干个等价类。SAM 的状态个数取决于等价类的个数,每一个状态对应若干个等价类。
根据等价类的定义有以下引理:
-
引理1:字符串 s 的两个非空子串 a,b (∣a∣≤∣b∣)为同一个等价类当且仅当 a 的每次出现都以 b 的后缀形式出现。
-
引理2:字符串 s 的两个非空子串 a,b (∣a∣≤∣b∣)。若 a 是 b 的后缀,则endpos(b)⊆endpos(a),否则endpos(a)∩endpos(b)=∅
-
引理3:一个等价类的所有字符串按照长度从小到大排序,长度恰好覆盖一个区间 [x,y],实际上这个区间就是最短串长度到最长串长度。
引理3证明
设最大串为 a , 最小串为 b , 考虑所有 a 的长度大于 ∣b∣ 的后缀,都属于同一个等价类,因为对于一个后缀 x , b 的每次出现都以 x 的后缀出现(∣x∣>∣b∣),根据引理一:x,b,a,属于同一个等价类。
后缀连接link
以下设起始状态为空串,其endpos={−1,0,...,∣s∣−1}
SAM 每个非起始状态都对应一个等价类,记最长串为 a , 对于 a 的所有后缀,找出最长的且和 a 不是同一个等价类的后缀,该节点的后缀连接
连接到该后缀的 endpos 对应的节点(也就是该后缀属于的等价类的节点)。
每个状态一定连接到严格更短的子串,向上走一定能到达起始状态。这棵树也成为parent tree
。
构造
构造 SAM 为在线算法,每次以加入一个字符c构建。
在线性构造 SAM 前,每个状态定义len为最长串的长度,minlen为最短串的长度,根据后缀连接的定义:
minlen(v)=link(len(v))+1
现在开始构造 SAM ,我们设起始状态为 st , link(st)=−1,len(st)=0
定义一个辅助状态指针 last 为当前字符串构建时对应的状态,初始 last=0
现在加入一个字符 c ,会执行以下流程:
- 创建一个新的状态 cur,令len(cur)=len(last)+1
- 从last开始,若last没有向c的转移,则添加,并且跳后缀连接;若找到转移,则停止,记当前状态为p。
- 若第2步跳到了起始状态st,即跳到−1,则令link(cur)=0 跳至第7步。
- 令 p 向 c 的转移的状态为 q,分情况讨论:若len(q)=len(p)+1,则执行第5步,否则跳至第6步。
- 令link(cur)=q ,跳至第7步。
- 复制状态 q:新建一个状态 clone,
将 q 除了 len 的信息复制给 clone , len(clone)=len(p)+1,令link(cur)=clone,link(q)=clone,接着从状态 p 开始跳后缀连接,将所有指向 q 的转移改为指向 clone。
- 令 last=cur,构建结束。
将整个字符串构建完成后,从最终状态开始(last),跳后缀连接,所有非 st 的状态都为终止状态,从st到任意终止状态构成的子串一定为原字符串的后缀。
这里对第3,4,5,6步进行进一步解释:
第3步中,状态 p 存在到 c 的转移,为避免转移冲突(避免更改已有的转移),故不再跳后缀连接。
第4步中,我们有了转移 (p,q),设p状态对应的字符串为x,则该自动机中就添加了字符串x+c。
如何确定link(cur)的指向是问题,按照定义,指向的字符串应该是x+c,且长度为len(p)+1,若q满足len(q)=len(p)+1,则link(cur)=q;否则,转移不连续,就需要将q拆开,拆出一个len=len(p)+1的部分,记为clone,link(cur)=clone。比如构建"edfbcbc"的SAM,在构建最后一个"c"的时候,会跳到第一个"c",但我们显然不能把这个"c"和"edfbc"放到同一个状态(endpos不同),所以要复制出来一个。
最后需要重定向到q的转移,设状态p的最长字符串的所有后缀为w,对w+c重定向转移即可,所以跳parent tree直到起始节点。
如果不理解的话,可以模拟对"abbb"构建SAM的过程,这里给出结果图:

参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| void insert(int c) { int p=tot++; t[p].len=t[las].len+1; int now=las; while(now!=-1&&!t[now].ver[c]) { t[now].ver[c]=p; now=t[now].link; } if(now==-1) t[p].link=0; else { int q=t[now].ver[c]; if(t[now].len+1==t[q].len) t[p].link=q; else { int clone=tot++; t[clone].len=t[now].len+1; t[clone].link=t[q].link; for(int i=0;i<=25;i++) t[clone].ver[i]=t[q].ver[i]; while(now!=-1&&t[now].ver[c]==q) { t[now].ver[c]=clone; now=t[now].link; } t[q].link=t[p].link=clone; } } las=p; }
|
应用
直接在 SAM 上从初始状态跑转移即可。
本质不同:每个状态对应一个等价类,根据引理,每个状态的所有串长度恰好覆盖区间一个区间,所以状态 p 的本质不同子串个数为:
maxlen(p)−minlen(p)+1=maxlen(p)−(maxlen(link(p))+1)+1=maxlen(p)−maxlen(link(p))
根据同样的推理方法可以推出不同子串的总长度。
仅位置不同:先计算每个状态的本质不同的子串个数,该状态仅位置不同的个数即为:本质不同子串个数×endpos大小。
如何求endpos大小?把目光放到parent tree上,该状态的子树的所有状态的endpos都代表该状态endpos的子集,根据 SAM 的性质,该状态的子状态的大小即为其endpos大小,进行一次 dfs 即可。
例题:[模板]后缀自动机 (SAM),[TJOI2015]弦论
文本串 t 对于模式串 s 的早出现位置,需要先找到 t 在 s 中的状态位置,其最早出现位置即为最小 endpos 。在加入点p时最小 endpos=len(p)−1,在复制点q时,最小endpos为q的最小出现位置。
同理所有出现位置即为子树的所有最早出现位置。
设为 s , t
后文介绍的 广义SAM 会提及,这里介绍 普通SAM 的解决方法:
对 s 构建 SAM ,遍历 t 的所有前缀,在 s 上找与 t 匹配的最长后缀,具体的:
设p=t,l=0,每次添加一个新得字符c:
存在p到c的转移,则转移,l自增
若不存在,就要跳后缀连接,直到回到初始状态或找到转移,若回到初始状态,就重设p=t,l=0重新开始。
广义SAM
顾名思义就是对多个字符串构建一个SAM
先说明几种假的做法
- 多个串合并成一个串构建
正确性没问题,但复杂度危险。
- 构建完一个串后将 last 归 0 重新构建下一个串
正确性是假的。
为什么假了
考虑单串SAM情形,添加一个字符c的时候,last一定没有向c的出边,但在广义SAM上,last可能会出现c的出边,如果这个转移是不连续的( len(q)>len(p)+1),程序会复制一个节点,这时候会发现最初新建的cur是个多余的节点,clone有它所有的属性,于是cur变成了一个空节点!
空节点的产生对于极少数情况计算siz,基排都产生了影响,所以就假了,只不过大多数题不会卡掉这种情况。
离线构造
正确的方法是将多个串压入一棵trie树,从低层向高层dfs/bfs建立 SAM ,这里只需要将last设置成根到当前trie节点的父亲构成的前缀串在 SAM 的状态编号。
注意,DFS在多模式串插入的复杂度为O(∑∣S∣),但在直接给一棵trie的情况下复杂度为O(∣T∣2),回溯造成了过多冗杂操作。而BFS时间复杂度不变。
在线构造
根据前文提到的假做法,需要加入特判:
- last存在向c的出边且转移连续,不需要构建直接返回,若转移不连续,则直接复制转移节点并退出而不再新建节点cur。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| int insert(int c,int las) { if(ver(las,c)) { int now=las,q=ver(las,c); if(len(now)+1==len(q)) return q; else { int clone=++tot; len(clone)=len(now)+1; for(int i=0;i<=25;i++) ver(clone,i)=ver(q,i); link(clone)=link(q); while(now!=-1&&ver(now,c)==q) { ver(now,c)=clone; now=link(now); } link(q)=clone; return clone; } } }
|
应用
每个状态新建一个cnti,j数组,表示状态i被字符串sj经过了cnti,j次,在新建节点的时候更新cnt,最后跑一遍dfs,按照len从大到小的顺序将该节点cnt加到link上去,最后随便拿出一个字符串,像两个串最长公共子串
一样,跑转移即可,转移可行的条件为对于所有的k(字符串数量),cntp,k>0。
带区间限制的一些问题
有些题目要求给定一个文本串s和多组模式串t,要求只使用s的一个子串和模式串进行匹配。
基于这类问题的解法,需要先讨论全局匹配的情况(即没有区间限制),进而得到带区间限制的情况。
此类问题一般对s建立SAM,我们对parent tree跑一遍 dfn序,在dfn序上跑线段树解决。
CF1037H Security
待更,如果忘了的话,就忘了吧(提醒一下)。