后缀自动机的一点点理解 by yyb

发布于 2018-02-13  191 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:后缀自动机的一点点理解 by yyb

后缀自动机的一点点理解

潜在可能格式挂了,yyb博客地址

前言

最近心血来潮,想学学SAM,于是花了一晚上+一上午
勉强打了出来(但是还是不理解)
虽说张口就讲我做不到
但是一些其他的东西还是有所感触的
索性,乱口胡点东西,谢谢关于SAM的一些简单的理解

资料

丽洁姐WC PPT
hihocoder上的后缀自动机

一些概念

这些概念都不读懂,接下来真的是步履维艰

本来我们要的是一个能够处理所有后缀的数据结构
但是我们发现,如果对于每一个后缀都要插入进Trie树
空间复杂度完全背不动($$O(n^2)$$级别)
于是,后缀自动机出现了
后缀自动机相比于Trie树
在空间上有了很大的改善,他的空间复杂度是$$O(n)$$级别的
(详见丽洁姐的PPT)

杂七杂八的没有什么太多写的必要,网上一找一大堆
写写一些概念

right/endpos

hihocoder上写的是$$endpos$$集合
其他的大部分地方写的是$$right$$集合
这就是最基础的概念了
叫做$$endpos$$的话应该很好理解,所以我就写$$endpos$$吧
$$endpos$$就是一个子串结束位置组成的集合
对于所有结束位置相同的子串
也就是$$endpos$$相同的两个子串
他们一个一定是另一个的后缀

至于证明,简单的想一下,如果一个子串出现在了若干个位置
那么他的后缀也一定出现在了这些位置(只可能出现在更多未知,不可能更少)

同时,得到了一个推论:
两个字符串如果有一个是另一个的后缀,
那么,较长串的$$endpos$$一定是较短串的$$endpos$$的子集
(就是上面写的,只可能多,不可能少)
同样的,如果没有后缀的关系,那么它们的$$endpos$$的交集一定是空集

而后缀自动机的每个节点就是依照$$endpos$$来划分
对于$$endpos$$相同的子串,我们可以划分在一起
我们不难得出一点,对于一堆$$endpos$$相同的子串
他们一定互为后缀,并且他们长度连续

首先证明互为后缀,那就是上面的那个推论,
如果不是互为后缀的话,$$endpos$$就不可能相等
而长度连续?
既然互为后缀,那就一定有一个最长的串,不妨记为$$longest$$
那么,所有的其他串一定是他的后缀
随着后缀长度的减小,
那么从某一个后缀开始,就可能出现在了更多的位置
那么,这个后缀以及比它更短的后缀的$$endpos$$一定会变大
此时他们就会分到别的节点去了
因此,具有相同$$endpos$$的子串一定长度连续,互为后缀
另外一个简单的结论,确定了$$endpos$$和长度$$len$$就能确定唯一的子串

trans

$$trans$$不难理解是转移的意思
设$$trans(s,c)$$表示当前在$$s$$状态,接受一个字符$$c$$之后所到达的状态
一个状态$$s$$表示若干$$endpos$$相同的连续子串
那么,此时相当于在后面加上了一个字符$$c$$
那么,我们对于任意一个串直接加上一个字符$$c$$之后
组成的串的$$endpos$$还是相同的
所以$$trans(s,c)$$就会指向这个状态
换句话说,随便在当前状态$$s$$中找一个串(比如$$longest$$)
然后在后面接上一个$$c$$
那么,就指向包含这个新字符串的状态

Parent/Suffix Links

本质上也是一个东西,不同的地方写的不一样而已
不妨设一个状态中包含的最短的串叫做$$shortest$$
那么,我们就知道$$shortest$$的任意一个非自己的后缀一定就会出现在了更多位置
他的最长的那个后缀,也就是减去了第一个字符后的串
就会出现在另外一个状态里面,并且是那个状态的$$longest$$
为什么?因为出现在了更多的位置,我们还是知道他是连续的子串
如果存在一个更长的串
那么,只可能是当前状态的$$shortest$$,
但是$$shortest$$属于当前状态,而没有出现在更多的位置
因此,$$longest$$一定是当前状态的$$shortest$$减去最前面字符形成的串

那么,当前位置的$$parent$$就会指向那个状态

当然,还是有几个很有趣的性质
假设当状态是$$s$$
$$s.shortest.len=parent.longest.len+1$$
这个就是前面所说的东西,所以,对于每个状态,就没有必要记录$$shortest$$
因为你只要知道$$parent$$就可以算出来了

其次,$$s$$的$$endpos$$是$$parent$$的子集
这个不难证明,因为$$parent$$包含了更多的位置

如果$$trans(s,c)\neq NULL$$
那么,$$trans(parent,c)\neq NULL$$
因为如果$$trans(s,c)$$存在这个状态
那么$$parent$$的串加上$$c$$之后,一定还是$$s+c$$后的后缀
所以也一定存在$$trans(parent,c)$$
所以,你可以认为$$parent$$是一个完全包含了$$s$$的状态
也正因为如此,$$parent$$的$$endpos$$就是所有儿子$$endpos$$的并集

将所有的$$parent$$反过来,我们就得到了$$parent$$树
如果要处理什么,就需要$$parent$$树的拓扑序
(因为$$parent$$相当于包含了所有的他的子树,都需要更新上去)
其实不需要拓扑排序
我们知道$$s$$的$$endpos$$完全被$$parent$$的$$endpos$$包含
$$s.longest$$一定长于$$parent.longest$$
所以,一个状态的$$longest$$越长,它一定要被更先访问
所以,按照$$longest$$的长度进行桶排序就可以解决拓扑序了

extend

对于一个$$SAM$$的构造
我们当然在线了(因为我只会这个)
我们依次加入字符$$c$$,来进行构造

假设原来的字符串是$$T$$
首先,一定会有一个新节点
因为新加入了一个字符后,一定出现了这个新的字符串$$T+c$$
此时$$endpos$$一定是新的位置
同时,原来的$$T$$的最后一个位置也可以通过$$+c$$变到这个新位置
设原来的最后一个位置的状态是$$last$$,新的状态是$$np$$
所以$$trans(last,c)=np$$
根据前面的东西,我们知道$$last$$的祖先们一定也会有这个$$trans$$
我们要怎么解决他呀

令$$p=last$$
一直沿着$$parent$$往前跳,也就是不断令$$p=p.parent$$
所以$$p$$代表的,就是越来越短的$$T$$的后缀
因为要更新的是最后的位置,
只有当存在$$T$$的最后一个位置时才能更新

如果$$trans(p,c)=NULL$$,直接令$$trans(p,c)=np$$
很显然是可以直接在后面添加一个$$c$$到达$$np$$的
如果跳完后发现没有$$parent$$了,直接把$$np.parent$$指向$$1$$
也就是空串所代表的状态

如果某个$$trans(p,c)$$不为$$NULL$$
那么,设$$q=trans(p,c)$$
如果有$$longest(p)+1=longest(q)$$
什么意思?
在$$p$$的串后面添上一个$$c$$之后就是$$q$$状态
没有任何问题,直接在作为$$T$$的后缀的那一个子串上
直接添加一个$$c$$显然也可以到达$$q$$状态
又因为$$np$$所代表的$$endpos$$更小,
所以$$np.parent=q$$

在否则的话
也就是$$longest(q)>longest(p)+1$$
具体的反例看丽洁姐PPT第$$35$$页
如果直接插入的话(也就是$$np.parent=q$$)
相当于给$$q$$的$$endpos$$强行插入一个$$q$$
但是,我们发现,如果强行插入进去
这个$$T+c$$的后缀会出现在更多的位置,应该属于另外一个状态
然后就$$GG$$了
此时,我们新建一个点$$nq$$
相当于把$$q$$拆成两部分:
一部分是$$T+c$$的那个后缀,一个是$$longest(p)+c$$
也就是$$longest(nq)=longest(p)+1$$
显然$$T+c$$的后缀是包含了状态较少的,
拆分出来的一部分$$q$$是长度较长的
所以$$q.parent=np.parent=nq$$
同时,继续沿着$$p$$的$$parent$$往上走
把所有的$$q$$都替换成$$nq$$

看起来很有道理,但是我也是似懂非懂的感觉

End

这就是我自己的一些没有什么用的总结了
我觉得题目才能真正反映SAM的作用
到时候再补点题目上去

补一份后缀自动机$$extend$$的代码

int tot=1,last=1;
struct Node
{
    int son[26];
    int ff,len;
}t[MAX<<1];
void extend(int c)
{
    int p=last,np=++tot;last=np;
    t[np].len=t[p].len+1;
    while(p&&!t[p].son[c])t[p].son[c]=np,p=t[p].ff;
    if(!p)t[np].ff=1;
    else
    {
        int q=t[p].son[c];
        if(t[p].len+1==t[q].len)t[np].ff=q;
        else
        {
            int nq=++tot;
            t[nq]=t[q];t[nq].len=t[p].len+1;
            t[q].ff=t[np].ff=nq;
            while(p&&t[p].son[c]==q)t[p].son[c]=nq,p=t[p].ff;
        }
    }
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:后缀自动机的一点点理解 by yyb


我是蒟蒻yyb 我太弱了 我还要多切大火题 我才能变得像zsy那么优秀