后缀自动机笔记

本文用丽洁的PPT中的理论(Right集合,状态的min,max)来解释好了.

不过在细节上会和丽洁的有出入,比如蒟蒻太弱了受不了开区间表示.

可能丽洁的理论和程序实现关系不大不过确实能帮助你理解SAM

4.线性构造SAM

算法思想 增量法

初始化 直接root表示空串,类似Trie的root

假设串T的SAM构造完成,现在加入ch构造串 Tch 的SAM,记L=|T|

新建结点np,np.R={L+1},max(np)=L+1,其是接受态

只有L in s.R的状态s才有被修改的可能

考虑状态p=ST(T),现在p.R={L}

由Parent树可得所有L in s.R的s要不是p就是p的祖先.

设自底向上这些结点是v[1]=p,v[2]..v[k]=root.

考虑v[i],在v[i]后添加一个ch形成nv[i]

vi.R中只有S[ri+1]=ch的ri才合法即

nv[i].R={r'i+1 | (r'i in v[i].R)and(S[r'i+1]=ch) }

如果v[i]没有ch出弧则只有ri=L才是合法的,直接加连向np的ch弧

即trans(v[i],ch)=np

如果v[i]有ch出弧,由于故v[i+1]也一定有

令q=trans(v[i],ch),显然q.R={ (r'i+1 | r'i in v[i].R)and(S[r'i+1]=ch) }

但是我们不一定能直接把L+1加入q.R,反例如下图

蓝色初始态 红色接受态 红弧指向parent 其他都很普通

从左到右的R集合为

{1,2,3} {1,2},    {2}    {3}

此时T = [aab],加入ch=[b]

从左到右的R集合为

{1,2,3,4}  {1,2}   {2}  {3,4}    {4}

这个是v[i]  这个是q

但是Right(a)={3,4}的a只有[b],这就造成了第三个结点的max减少

或者你可以说是结点代表的子串混乱了.

当然如果max(q)=max(v[i])+1就不会产生这个问题因为

max(trans(v[i],ch))>=max(v[i])+1=max(q)不会造成max(q)减少

而由以下的正确建法便不会产生这个问题

正确建法

对于每个结点维护max域,代表该状态max(s)

维护last指针指向max(s)最大的状态s

每次如下执行算法
S1 新建np代表新结点,np.max=last.max+1,p=last

S2 如果p没有ch出弧,直接连ch出弧到np并且p=p.parent,继续S2

否则转S3

S3 q=trans(p,ch) 如果q.max=p.max+1则np.parent=q否则

新建nq,定义现在对任何ch,trans(nq,ch)=trans(q,ch)

nq.max=p.max+1,nq.parent=q.parent,q.parent=nq,np.parent=nq

从p开始往上的所有指向q的指针指向nq,算法完成

最后特判一下边界

二 后缀自动机的应用

1.最小表示法

给定S,求i使得从i开始的循环S表示字典序最小

对于串SS建立SAM,每次贪心走最小的转移边走完|S|步即可

最后求i可以用KMP

2.字符串匹配

给定模式P,文本T,进行串匹配

建立P的SAM,每次输入T当前位置的字符

如果当前位置有输入字符的转移弧直接转移即可

否则沿Parent指针走到第一个有该转移弧的状态或者根如果没有这样的状态

更新匹配长度.一旦发现匹配长度=|P|报告匹配

或者一旦走到s,s.R={|P|}则报告匹配

这提示我们SAM有一个功能

给出A,B,对于每个i,求出g[i]=max{j | B[i-j+1..i]是A的子串}

具体应用参见CTSC2012 Cheat

3.LCS

给定A,B,求LCS,LCS应该是连续的一段.

直接上上面SAM的功能即可

4.定长不同子串计数

给定S求S有多少个长度为L的不同子串

引用vfk的Hash Killer里面的话

“后缀自动机上代表的长度区间包含L的结点个数”

三 代码

可能"有点"压行

program Suffix_Automaton;

type pnode=^tnode;
     tnode=record
        max:longint;
        pre:pnode;
        next:array[1..26] of pnode;
     end;

var root,last,null:pnode;

procedure sam_init;
begin
new(null); with null^ do begin
        max:=-1; pre:=null; filldword(next,length(next),dword(null));
end;
new(root); with root^ do begin
        max:=0; pre:=null; filldword(next,length(next),dword(null));
end; last:=root;
end;

function newnode(imax:longint):pnode;
begin
new(newnode); with newnode^ do begin
        max:=imax; pre:=null; filldword(next,length(next),dword(null));
end;
end;

procedure add(ch:byte);
var p,np,q,nq:pnode;
begin
p:=last; np:=newnode(p^.max+1);
while (p<>null)and(p^.next[ch]=null) do begin p^.next[ch]:=np; p:=p^.pre; end;
if p=null then np^.pre:=root else begin q:=p^.next[ch];
        if p^.max+1=q^.max then np^.pre:=q else begin
                nq:=newnode(p^.max+1); move(q^.next[1],nq^.next[1],sizeof(q^.next));
                nq^.pre:=q^.pre; q^.pre:=nq; np^.pre:=nq;
                while (p<>null)and(p^.next[ch]=q) do begin p^.next[ch]:=nq; p:=p^.pre; end;
        end;
end; last:=np;
end;

begin
end.