上一篇我们学习了SAM的基本概念.通过转移函数知道了SAM的工作原理.现在来进一步做题.hihocoder#:后缀自动机二·重复旋律5,注意,为保证循序渐进,墙裂推荐先学习再来看本文.会发现本文是那么的自然.

时间限制:ms单点时限:ms内存限制:MB描述小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为一段数构成的数列。现在小Hi想知道一部作品中出现了多少不同的旋律？输入共一行，包含一个由小写字母构成的字符串。字符串长度不超过1e6。输出一行一个整数，表示答案。样例输入aab样例输出5

本题其实就是告诉你一个字符串S,然后问你S的所有不同子串的个数.而根据的学习,我们知道答案就是

所以我们必须构建出SAM.但是字符串的长度达到了1e6,所以必须采用O(len(S))的SAM构造算法.本文的目的就是学习SAM的线性时间构造算法.

和后缀树一样,我们打算采用增量的观点来构造SAM.所谓增量的观点就是每次读入一个字符.则会新产生一些要识别的后缀.然后我们就必须对现有的SAM进行改造.最终等到所有的字符都读完之后,整个字符串的SAM就构造好了.举个例子——我们要构造S="abaab"的SAM,则从空串开始，空串对应的SAM就是SAM的0起点.然后依次读入a、b、a、a、b这5个字符,每次都会对既有的SAM进行升级改造.读完最后的b并且升级改造完毕就得到了S="abaab"的SAM.因为我们需要O(n)构造算法.所以我们不难想象,每次的升级改造SAM的时间必须控制在O(1)内.这个时候,你就会发现后缀link（下面简称slink）帮了大忙——所以中才说slink是SAM的大杀器.

好了,现在来看看假如我们已经读完了S[i]并且升级改造完毕了SAM.假设S[1,...,i]位于的节点是u.现在需要读入S[i+1]这个字符.则我们新增的需要识别的后缀是S[1,...,i+1],S[2,....,i+1],S[3,....,i+1],.....S[i,i+1],S[i+1].而这i+1个后缀恰好就是S[1,...,i]、S[2,..,i]、...、S[i]、空串这i+1个后缀拼上S[i+1]形成的.而根据的学习,我们知道S[1,..,i]、S[2,...,i]、...、S[i]、空串这i+1个子串属于若干等价类,而且这些等价类对应的sam节点之间通过slink连接,而且沿着slink恰好走到sam的起点0（按照中的描述,删光了所有S[1,..,i]中的字符变成了空串,空串对应的节点就是sam起点0）.其中S[1,...,i]属于的节点称作u,则这条沿着slink的路径就是从u出发,一直走到sam的根节点0的路径.我们称之为slink-path(u)

ps:这里多说一句整个SAM的构造大体发生什么事情.以便读者对SAM的构造全貌有个清晰的认识.因为我们中也提到了.SAM是要识别所有子串的机器.而子串不就是前缀的后缀么(或者后缀的前缀,到底哪种观点来看待子串要根据具体情形)?所以SAM的构造过程是每次新读入一个字符S[i+1],则新产生的前缀是S[1,..,i+1],而它的所有后缀是S[1,..,i+1],S[2,..,i+1],...,S[i,i+1],S[i+1]这i+1个后缀.我们每次升级改造SAM其实就是要保证升级改造之后,这i+1个后缀在SAM中能被识别.或者说这i+1个后缀中任何一个都能找到一个节点作为归属.如果这i+1个后缀中有后缀在改造前的SAM中找不到节点作为归属的话，则就要新建节点来作为归属——即SAM产生了新的状态.注意,这i+1个后缀中不是每个后缀都要新建节点的.例如abba,读入S[4]=a,新增的4个后缀是abba、bba、ba、a,对于最后的那个后缀"a"而言,就不需要新建节点.因为既有的SAM中已经有节点可以作为它的归属了.但是我们可以断言每次升级改造至少会诞生一个新的节点,因为S[1,...,i+1]比当前任何前缀都要长.它不可能属于任何一个既有节点.

下面直接贴本题代码,后面会有详细注释

//#include"stdafx.h"#includestdio.h#includestring.h//#defineLOCALtypedeflonglongll;constintmaxn=1e6+5,SZ=26;intn;//n是sam节点个数,sam的节点标号从0开始(sam[0]是sam的起点状态)chars[maxn];structSamNode{　　inttrans[SZ],slink;　　intshortest,longest;}sam[maxn1];intnewnode(intshortest,intlongest,int*trans,intslink){　　sam[n].shortest=shortest;　　sam[n].longest=longest;　　sam[n].slink=slink;　　trans?memcpy(sam[n].trans,trans,SZ*sizeof(int)):memset(sam[n].trans,-1,SZ*sizeof(int));　　returnn++;}intinsert(charch,intu){　　intc=ch-a;　　intz=newnode(-1,sam[u].longest+1,0,-1);　　intv=u;　　while(~v!~sam[v].trans[c])　　{　　　　sam[v].trans[c]=z;　　　　v=sam[v].slink;　　}　　if(!~v)　　{　　　　sam[z].shortest=1;　　　　sam[z].slink=0;　　　　returnz;　　}//参见附录图1　　intx=sam[v].trans[c];　　if(sam[v].longest+1==sam[x].longest)　　{　　　　sam[z].shortest=sam[x].longest+1;　　　　sam[z].slink=x;　　　　returnz;　　}//参见附录图2　　inty=newnode(-1,sam[v].longest+1,sam[x].trans,sam[x].slink);　　sam[x].shortest=sam[y].longest+1;　　sam[x].slink=y;　　sam[z].shortest=sam[y].longest+1;　　sam[z].slink=y;　　while(~vsam[v].trans[c]==x)　　{　　　　sam[v].trans[c]=y;　　　　v=sam[v].slink;　　}　　sam[y].shortest=sam[sam[y].slink].longest+1;　　returnz;//参见附录图3}intmain(){#ifdefLOCAL　　freopen("d:\\data.in","r",stdin);//　　freopen("d:\\my.out","w",stdout);#endif　　scanf("%s",s+1);　　intu=newnode(0,0,0,-1);　　inti=1;　　while(s[i])　　{　　　　u=insert(s[i],u);　　　　++i;　　}　　llans=0;　　for(i=1;in;i++)　　{　　　　ans+=sam[i].longest-sam[i].shortest+1;　　}　　printf("%lld",ans);　　return0;}

下面解释一下上面的代码

line7n是sam节点个数,sam的节点标号从0开始(sam[0]是sam的起点状态)line12trans[i]表示当前sam节点读取i+a之后跳转到sam的哪个节点.slink是后缀link,此乃sam本身必须的2个字段line个业务字段,longest表示一个状态节点最长的子串长度,shortest表示一个状态节点最短的子串长度,从而longest-shortest+1就是该节点表示的等价类中包含的子串个数,为什么说是业务字段?因为本题就是要求不同子串的个数,所以每个节点要有这两个字段.如果是处理字符串的别的具体问题,则这两个业务字段是不需要的——即非sam本身必须字段line14为什么要开两倍节点?因为看下面的add_char方法就知道每次升级改造SAM的时候,至少要新增一个节点z,而且遇到要分裂的情况的时候,还会新诞生一个节点,也就是每次至少产生2个节点,所以需要开2倍的空间line16新建一个sam节点,并返回此节点的标号line22则最后sam的节点就是[0,...,n-1],其中0是自动机起点line25u是s[1,..,i]所属的sam节点标号,ch是当前读入的字符,则我们就要对SAM进行升级改造,称升级改造之前的sam为sam(i)（表示读入S[i]并改造完毕的sam）.函数返回S[1,...,i+1]所属于的节点line28因为新建的这个节点z就是S[1,...,i+1]这个子串属于的节点,当前来讲,最长肯定是i+1,其实就是u=S[1,..,i]所属的sam节点的最长（即i）+1line30v沿着slink-path(u)往0走line32因为sam[v].trans[c]是-1,表示v节点中的子串读入c之后在sam(i)中无路可走,那么就只能走到z去(因为根据中提及的推论,v节点中的子串读入字符c,都将跑到同一个、别的等价类中去,而这个等价类在sam(i)中找不到)line35如果整条slink-path(u)上——从u跑到0(sam起点)所有的状态节点读入c之后在sam(i)中都找不到节点收容,则都跑到z去了line37说明z节点中最短的子串长度就是1line38只有删光了S[1,..,i+1]中所有的字符才能发生状态转移(即endpos集合才会发生变化,这里的描述可以参见),而且是转移到sam起点0line39改造完毕,返回结果line41slink-path(u)从u开始往0走,考察经过的每个节点读入c字符之后的状态转移情况,伊始全是-1,但是突然冒出一个x,即-1,-1,....,-1,x即slink-path上突然有节点v读入c之后有路可走了,并且路是从v读入c之后转移到了x状态节点line44这一行是下一行的推论(参见的推论)line45我们考虑z的slink的定义——根据,不就是不停的删减字符之后第一次发生质变的时候跳转到的状态吗?而在slink-path(u)上v之前的节点读入c之后都是跳到z(因为在sam(i)中找不到归宿),说明一直没有质变.而到了v的时候,读入c之后就是跳到x而不是跳到-1了.这说明发生了质变,所以按slink的定义,我们有slink(z)=x,但是我们得问一下x有没有因为ch的读入发生变化呢?正因为如此,我们才要判断一下sam[v].longest+1与sam[x].longest之间的关系,注意,根据的推论,我们知道sam[v].longest+1=sam[x].longest.所以sam[v].longest+1和sam[x].longest之间的关系只有==与,如果是==的话,则说明状态x并没有因为ch的读入而变化,如果是的话,则说明x状态因为ch的读入而变化了————确切讲是x要分裂了,因为x中比较短的一部分子串已经可以出现在i+1位置了(即endpos集合中新增了i+1),而比较长的那些字符串依旧不能在i+1位置出现(即endpos集合中没有i+1),所以endpos不相等了,出现了断层,所以不再在一个等价类中了,所以x要分裂了.line48拆分x（需要拆分的原因见第45行代码）,而且注意,x和y的trans是一样的哈,这本质也是的推论决定的.line49从x拆出一个节点y,然后剩下的部分留作x,因为剩下的部分到y的长度是连续递减的,所以剩下的部分作为节点的slink应该指向yline51下一行代码的推论line52根据slink的定义.因为我们想知道z的slink指向谁的话,就要不断的将S[1,...,i+1]删减字符,直至发生质变(这里的描述见).而S[1,..,i+1]删减字符其实就是S[1,..,i]删减字符,删完再拼接一个字符S[i+1],而S[1,..,i]其实是slink-path(u)上节点代表的子串集合的不交并.但是v之前的节点删完字符再拼上S[i+1]都一直是跳到z的(参见32行代码).并没有发生质变,只是在v这里发生了质变——跳到了y（注意,x已经因为ch的读入而发生了分裂,所以是跳到y,而不是x了）.所以sam[z].slink=yline53将沿着slink-path(u),从v继续出发往0走.将原先转移到x的都改成转移到yline58根据的推论line索引不用,因为根据上面的论述,我们的前缀都是S[1,..,i],所以索引都是从1开始的line69初始化sam起点0,该节点里面的子串仅有空串,所以shortest、longest都是0.line73每次读入一个字符,升级改造既有samline76防止答案爆int

通过本题，我们就能体会到为什么slink是SAM能O(n)构建的保证了.因为我们每次升级改造的过程本质上是完成识别S[1,...,i+1]、S[2,....,i+1]、....、S[i,i+1]、S[i+1]的任务——所谓的识别也就是给这i+1个后缀都找到归属的节点——如果找不到就新建SAM节点.如果没有slink的话,我们就要逐个去考察这些后缀,看看他们属于哪个节点.一旦这样,算法就膨胀为O(N^2)的了.而后缀link的最大也是唯一作用在于已经帮我们维护好了S[1,...,i]、S[2,...,i]、.....S[i-1,i]、S[i]、空串的归属了（而我们要新增的i+1个后缀恰好就是这i+1个后缀后面拼接上S[i+1]这个字符而已）——类似于分块的思想.而且他们之间的归属通过slink已经帮我们维护好了.我们通过slink就可以快速的从一个节点跳到另一个节点,就不需要傻傻的一个一个的遍历这些后缀了.复杂度就降低为O(n).这就是slink的威力!其实对比后缀树的ukk算法，也都用到了类似的思想——就是快速维护.后缀树的构建也用到了后缀链接的思想.

《史上全网最清晰后缀自动机学习(一)基本概念入门》

温馨提示

如果你喜欢本文，请分享到朋友圈，想要获得更多信息，请
转载请注明原文网址：http://www.lechangzx.com/lcsjj/10221.html