最长公共子串（LCS）问题可谓是经典的问题了.我们使用过DP、后缀树、后缀数组来解决过.现在我们考虑后缀自动机和LCS问题的联系,并且来看这一联系的典型例题——hihocoder#:后缀自动机五·重复旋律8
分析时间限制:ms单点时限:ms内存限制:MB描述小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一段音乐旋律可以被表示为一段数构成的数列。小Hi发现旋律可以循环，每次把一段旋律里面最前面一个音换到最后面就成为了原旋律的“循环相似旋律”，还可以对“循环相似旋律”进行相同的变换能继续得到原串的“循环相似旋律”。小Hi对此产生了浓厚的兴趣，他有若干段旋律，和一部音乐作品。对于每一段旋律，他想知道有多少在音乐作品中的子串（重复便多次计）和该旋律是“循环相似旋律”。解题方法提示输入第一行，一个由小写字母构成的字符串S，表示一部音乐作品。字符串S长度不超过0。第二行，一个整数N，表示有N段旋律。接下来N行，每行包含一个由小写字母构成的字符串str，表示一段旋律。所有旋律的长度和不超过0。输出输出共N行，每行一个整数，表示答案。样例输入abac3aabca样例输出
首先,本题是涉及子串的题目,所以考虑使用后缀自动机解决.
首先来理解一下题意.
这道题目让我们求的是若干串T在另一个长串S中各自作为子串出现的次数,只是匹配的方式从完全相等变成了“循环同构”。如果匹配方式是完全相等的话,则就可以使用AC自动机解决。
但是本题比较恶心的地方在于匹配的方式改成了循环同构.比如T="abcd"的话，我们要判断4个串"abcd","bcda","cdab","dabc"在S中出现的次数。
首先,对于这种循环同构的问题,有一个常见的技巧.例如T="abcd",则将T改造成T1="abcdabc"——即将T[1,...,len(T)-1]拼在T的后面构成T1.则T1中就很自然的包含了T="abcd"的所有4个循环同构了.那么得到T1之后,我们就只需要去研究T1和S之间的LCS（最长公共子串）问题了.我们使用过后缀树、后缀数组研究过LCS的=O(nlogn)算法.现在很荣幸,使用SAM也来切一次LCS问题.
现在,我们开始考虑用后缀自动机解决串S和T的LCS问题.
首先我们构造S的sam,然后对于i（1=i=len(T)）,我们想要确定以T[i]为结尾的LCS属于哪一个sam状态节点u以及最长能匹配多长l.即对于每个1=i=len(T),我们要确定最大的l,使得T[i-l+1,...,i]也作为S的子串.而S的sam是一部恰能识别所有S子串的机器（这个说法在中已经说过了）.所以我们其实就是要求最大的l,使得T[i-l+1,...,i]喂入S的sam之后不会出现无路可走的情况,即一定能最终停留在某个SAM的节点处.
现在我们从T[1]开始,一个一个字符T[i]的喂S的后缀自动机吃.期间维护两个变量u和l,其中l是最大的使得T[i-l+1,...,i]能读入sam之后不会出现无路可走的情况的数.u是T[i-l+1,...,i]所属的sam节点.
我们依旧归纳的考虑这个问题.
最开始时,我们得到了空串的u和l,显然,u=0,l=0
假设我们已经得到了T[i]为结尾的最长匹配串——长为l,并且SAM读入此匹配串T[i-l+1,...,i]之后将停留在sam的节点u。则我们考虑以T[i+1]为结尾的最长匹配串.假设其长度为l1,并且sam读入T[i+1-l1+1,..,i+1]之后sam将停留在u1节点.
其实在中已经用过了这个观点——就是T[i+1]为结尾的最长匹配串其实就是T[1,..,i]的某个后缀拼接上T[i+1]而已.而前缀T[1,...,i]的所有后缀其实就在slink-path(u)上（slink-path(u)的论述参见）.所以我们要想找到以T[i+1]为结尾的最长匹配串,其实只需要沿着slink-path(u)往0走,遇到第一个读入T[i+1]之后不会跳转到null（即无路可走）的节点.假设这个节点是v,即v.trans[T[i+1]-a]=x,x!=null,那么l1=
longest(v)
+1,u1=x（为了保证求最长,这是显然的）
如果整条slink-path(u)一路上都没有节点v能使得读入T[i+1]这个字符之后能跳转到某个节点去而不至于无路可走的话,则S中一定没有T[i+1]这个字符.这也是显然的,因为如果S中存在T[i+1]这个字符的话（假设S[b]=T[i+1]）,至少0节点(0节点也在slink-path(u)上哦~)读入T[i+1]之后能走到一个合法节点吧~因为你考虑一下后缀S[b,...]就知道从0读入S[b]=T[i+1]之后就能跳到一个合法节点吧~如果S中不存在T[i+1]这个字符的话,则T[i+1]为结尾的最长匹配串显然l1=0,u1=0（不能停留在后缀自动机的任何0的合法顶点处）,即回归起点重新开始了——继续读入T[i+2]去了.
所以我们使用SAM作为工具,就O(
S
+
T
)时间内完美的解决了LCS问题。因为我们只需要取T[i]们中的最大l,就知道LCS(S,T)长什么样子——T[i-l+1,...,i],如果你想知道T[i-l+1,...,i]在S的哪个索引出现,也是可以线性时间知道的.大不了再做一次KMP（或者直接偷懒用c++APIstrstr就行了）嘛~反正又不增加复杂度
至此,使用后缀自动机解决LCS问题考虑完毕
现在想想看,如何将上面的LCS问题的结论运用到本题中.我们说了,首先使用T构造T1,然后考虑LCS(S,T1)问题.从T1[1]开始不断的喂入S的sam字符,期间维护u和l（注意,这里的u和l和上面的LCS问题的u和l的意义稍有不同,这里的u和l除了满足T[i+1]为结尾的匹配串之外,还要满足l=n(这里n是T的长度)且u包含后缀T[i+1-n+1,..,i+1]）.找到此过程的v（v指什么,见上面LCS的分析）之后,令u是v读入T[i+1]之后跳转的节点.l要自增1（因为拼接上了T[i+1]嘛~）,不要急,此时,u和l还没求完,
如果l=n的话,则能保证T1[i+1-l+1,...,i+1]在u中,既然l=n,则长度为n的子串T1[i+1-n+1,...,i+1]（即T的一个循环同构）是T1[i+1-l+1,...,i+1]的后缀.即T1[i+1-n+1,...,i+1]是T1[i+1-l+1,...,i+1]删减字符（l=n的话,则不需要删减字符）得到的结果.所以T1[i+1-n+1,...,i+1]的endpos集合的大小（即出现的次数）=T1[i+1-l+1,...,i+1]的endpos集合的大小=
u.endpos
.所以我们并不能从sam节点u的endpos属性得到匹配串T1(i+1-n+1,...,i+1)出现的次数.
How?
显然,如果l=n的话,T1(i+1-l+1,...,i+1)=T1(i+1-n+1,...,i+1),所以T1(i+1-n+1,...,i+1)这个T的循环同构出现的次数就是u.endpos.则T[i+1]时的u和l就求完了.如果ln的话呢?我们就要继续删减字符——即沿着slink-path(u)从v继续出发往0走,直至v是slink-path(u)上最后的那个满足v.longest=n的v为止）.则T1[i+1]对应的u和l就应该是这个最后的满足v.longest=n的v（因为T1[i+1-n+1,...,i+1]属于v节点），而l应该是v.longest.
还有一个问题,就是维护上述u和l完毕之后,怎么更新答案的问题.讲道理,如果求解出了合理的u和l的话,则答案应该增加u.endpos——这很显然啊~因为合理的u和l意味着一个长度为n的T1的子串(其实就是T的一个循环同构)属于u节点,而且u节点的endpos属性恰好就是u中任何一个子串在S中出现的次数.所以答案要新增u.endpos.
但是如果T的循环同构有重复呢?比如T=aa,则T1=aaa,则考虑T1[2]和T1[3]的u和l时候就会重复更新答案了——即重复统计aa在S中出现的次数.
怎么办呢?其实,T1[2-n+1]和T1[3-n+1]（n=2）是相同的两个子串（都是"aa"）,所以沿着SAM走的话是会走到同一个节点u的.但是我们只能让u.endpos更新一次的答案,而不能用它更新2次.所以自然的,我们需要使用visited数组.让一个节点u仅仅参与一次的更新答案.这里就要回答一个问题——你怎么保证两次走到这个节点u的时候一定是T的相同的循环同构?很简单——因为sam的性质——同一个节点中的子串长度是连续严格递减1的（参见,所以sam的数学结构得有多优美!）.所以两个长度都为n的子串都走到sam的同一个节点一定是相同的子串,也就是同一个循环同构,所以要开一个bool的visited数组确保更新一次答案.
而一个节点的endpos大小在中通过slink树的方法已经解决了.
另外,本题的多串对于上述算法并没有什么影响~一个一个来就好了~
好了,说了这么多.开心的切代码好伐~
//#include"stdafx.h"#includestdio.h#includestring.h//#defineLOCALconstintmaxn=1e5+5,SZ=26;chars[maxn],t[maxn1];intn,len,head[maxn1],num;boolvis[maxn1];structArc{ intfrom,to,nxt;}g[maxn1];structSamNode{ inttrans[SZ],slink,longest,shortest; intendpos; boolflag;}sam[maxn1];voidaddarc(intfrom,intto){ g[num].from=from,g[num].to=to,g[num].nxt=head[from]; head[from]=num++;}intnewnode(intshortest,intlongest,int*trans,intslink,boolflag){ sam[n].shortest=shortest; sam[n].longest=longest; sam[n].slink=slink; sam[n].flag=flag; sam[n].endpos=flag; 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,true); intv=u; while(~v!~sam[v].trans[c]) { sam[v].trans[c]=z; v=sam[v].slink; } if(!~v) { sam[z].slink=0; sam[z].shortest=1; returnz; } intx=sam[v].trans[c]; if(sam[v].longest+1==sam[x].longest) { sam[z].slink=x; sam[z].shortest=sam[x].longest+1; returnz; } inty=newnode(-1,sam[v].longest+1,sam[x].trans,sam[x].slink,false); sam[x].slink=sam[z].slink=y; sam[x].shortest=sam[z].shortest=sam[y].longest+1; 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;}intkk(){ memset(vis,0,sizeof(vis)); intans=0,u=0,l=0,i=1,c; while(t[i]) { c=t[i]-a; while(u!~sam[u].trans[c]) { u=sam[u].slink; l=sam[u].longest; } if(~sam[u].trans[c])//和ac自动机跳fail类似(参见的58~62行以及77~81行) { u=sam[u].trans[c]; ++l; } else { u=l=0;//重新从0开始 } if(llen)//不要急,此时,u和l还没求完, { while(sam[sam[u].slink].longest=len) { u=sam[u].slink; l=sam[u].longest; } }//此时u和l已经求完了 if(l=len!vis[u])//防止重复的循环同构重复计数 { vis[u]=true; ans+=sam[u].endpos; } ++i; } returnans;}voidslinktree(){ memset(head,-1,sizeof(head)); for(inti=1,to;in;i++) { to=sam[i].slink; if(~to) { addarc(to,i); } }}voiddfs(intcur){ for(inth=head[cur],to;~h;h=g[h].nxt) { to=g[h].to; dfs(to); sam[cur].endpos+=sam[to].endpos; }}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,true),i=1; while(s[i]) { u=insert(s[i],u); ++i; } slinktree(); dfs(0); intkase; scanf("%d",kase); while(kase--) { scanf("%s",t+1); len=strlen(t+1); inti=1; while(i=len) { t[len+i]=t[i]; ++i; } t[len+i-1]=0;//构造T1 printf("%d\n",kk()); } return0;}
ac情况
Accepted参考
《史上全网最清晰后缀自动机学习(一)基本概念入门》
《史上全网最清晰后缀自动机学习(二)后缀自动机的线性时间构造算法》
《史上全网最清晰后缀自动机学习（三）后缀自动机里的树结构》
《史上全网最清晰后缀自动机学习（四）后缀自动机里的DAG结构》
温馨提示
如果你喜欢本文，请分享到朋友圈，想要获得更多信息，请