SPOJ LCS Longest Common Substring (后缀自动机模板题)

题意:

给出2个字符串(2.5E5),问最长公共子串的长度。

思路:

拿一个串建SAM

由于SAM上的任何一个状态,都对应一个或者若干个子串,然后拿另一个串在SAM上面跑就行了

20171110UPdate:我好像说得太简略了。。

参考clj的冬令营讲稿:

  • 给两个长度小于100000的字符串A和B,求出他们的最长公共连续子串。 Ê我们构造出A的后缀自动机SAM
  • 对于SAM的每个状态s,令r为Right(s)中任意的一个元素,它代表的是结束位置在r的,长度在[Min(s),Max(s)]之间的所有子串。
  • 我们不妨对状态s,求出所有B的子串中,从任意r开始往前能匹配的最大长度L,那么min(L,Max(s))就可以更新答案了。
  • 我们考虑用SAM读入字符串B
  • 令当前状态为s,同时最大匹配长度为len Ê我们读入字符x。如果s有标号为x的边,
  • 那么s=trans(s,x),len = len+1 Ê否则我们找到s的第一个祖先a,它有标号为x的边,令
  • s=trans(a,x),len=Max(a)+1。 Ê如果没有这样的祖先,那么令s=root,len=0
  • 在过程中更新状态的最大匹配长度

 

唯一不显然的地方在于,为什么当失配时,我们是沿着parent树向上找。

考虑如下例子:

 

我们知道,parent树,或者叫后缀链树,一个状态S指向的是,总起点开始到S的子串的后缀中,长度最长的后缀,满足该后缀所对应的某个状态Q(对应的意思是说,从初始状态到状态Q表示的子串恰好是该后缀)的right集合和状态S的集合不相等。

 

假设我们目前匹配到的状态表示的子串是abcbc,然后下一位要匹配的字母是b,而状态abcbc没有通过b转移的边(这些图上没有,我懒得画了orz)

这个时候考虑回退…对于abcbc的后缀,bcbc,cbc和abcbc面临的情况是一样的,因为bcbc,cbc,abcbc三个字符串的right集合相同,也就是出现的位置完全相同,那么既然abcbc没有通过b转移的边,bcbc,cbc也一定没有通过b转移的边。

这时候考虑转移到abcbc的par状态,也就是表示子串bc的状态,原因是bc的right集合和abcbc的right集合不同,更准确得说,bc的right集合是包含abcbc的right集合的。

而bc在之前匹配abcbc的时候,已经匹配过了,也就是说bc一定是可以匹配的,

如果此时bc有一条通过b转移的边,此时匹配的长度就变成了bc对应的状态所对应的max再+1

 

 

 

老年人的第一个SAM

关于SAM的笔记之后补。

用了动态的写法.

 

不过还是比较喜欢写静态的?

参考了zqc大爷的代码风格:

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz