求最长回文子串与最长重复子串
-
求最长回文子串与最长重复子串。
长沙雅礼中学
何林
【介绍】
问题的提出：
问题
1
最长回文子串
顺序和逆序读起来完全
一样的串叫做回文串。比如
acbca
是回文串，而
abc
不是（
abc
的顺
序为“
abc
”
，逆序为“
cba
”
，不相同）
。<
/p>
输入长度为
n
的串
S
，求它最长回文子串。
问题
2
最长重复子串
如果一个串
x
在
S
中出现，并且
xx
也在
S
中出现
，那么
x
就叫做
S
的重复
子串。
输入长度为
n
的串
S
，求它的最
长重复子串。
本文主要涉及“最长
回文子串”和“最长重复子串”这两个经典的信息学问
题。把他们放在一起讨论，是因为
两者的解法具有惊人的类似性。
从算法的最优性上说，两者都
存在线性时间复杂度的算法——使用后缀树。
无庸置疑，
后缀树
已经成了优化字符串处理类问题的不二法门。
但是它有两个致
命
缺点。
后缀树的时空复杂度和字符串涉及的字符集有直接关系
。
称后缀
树是
“线
性数据结构”也是建立在字符集规模为常数的假设上。
因此，所谓“线
性算法”
，准确的说，只是“伪线性”
。
实践后缀树的编程复杂度极高
。
如果说上一点是后缀
树在理论上的硬伤，
那么这一点就是后缀树在实践上的致命弱点。对时间要求很高的信息
学
竞赛，是不允许选手花数个小时去编写一个长而容易出错的程序的。最
重要的一点是，因为字符集比较大，后缀树的实际运行效果往往不佳，
甚至很容
易发生空间上的爆炸。
以上两个原因限制了后缀树在竞赛中的
应用，
虽然它在理论上的价值是不可
取代的。
< br>
一种折衷的数据结构——后缀数组——可以很好的平衡后缀树的缺点。
但是
其编程复杂度也不低。
要求任意两个串的最
长公共前缀，
或者用
RMQ
算法、
或者
用线段树，
这两只
“老虎”
都不是好惹的——几百行的程序一稍不留神就可能满
盘皆错。
本文重点介绍的是一个
有别于
“后缀”
系列的全新的算法：
分
治
+
扩展的
KMP
算法。
它时空复杂度低，
编程十分简单，
< br>而且算法原理非常好理解。
更重要的是
其解题思想有很深
的可挖掘性。
【扩展的
KMP
算法】
问题的提出：
扩展的
KMP
问题
给定母串
S
，和子串
T
。定义
n=|S|, m=|T|
，
extend[i]=S[i..n]
与
T<
/p>
的最长公共
前缀长度。
请在线性的时间复杂度内，求出所有的
extend[1..n]
。
容易发现，
如果有某个位置
i
满足
extend[i]=m
，
那么
T
就肯定在
S
中出现过，
并且进一步知道出现首位置是
i
——而这正是经典的
KMP
问题。
因此
可见“扩展的
KMP
问题”是对经典
K
MP
问题的一个扩充和加难。
来看一个例子
S=
’aaaaaaaaaa
baaa
’,
T=’aaaaaaaaaaa’
。
extend[1]=10
a a
a a a a a a a a b a a a
红色箭头表示失配
在第
11
个位置失配
a a a a a a a a a a a
这里为了计算
extend[1]
，我们进行了
11
次比较运算。
然后我们要算<
/p>
extend[2]
：
a a a a a a a a a a b a a
a
红色箭头表示失配
在第
11
个位置失配
a a a a a a a a a a
a
ex
tend[2]=9
。为了计算
extend[2]
，我们是不是也要进行
10
次比较运算呢？
不然。
因
为
通
过
计
算
extend[1]=10
，
我
< br>们
可
以
得
到
这
样
的
信
息
：
S[1..10]=T[1..1
0]
S[2..10]=T[2..10]
< br>。
计算
extend[2]<
/p>
的时候，
实际上是
S[2]
开始匹配
T
。
因为
S[2..10]=T[2..10]
，
所
以在匹配的开头阶段是“以
T[2..10]
为母串，
T
为子串”的匹配。
不妨设辅助函数
next[i]
表示
T[i..m]
与
T
的最长公共前缀长度。
.T[2..11]=T[1..10
]
T[2..10]=T[1..9]
S[2..10]=T[1..9]
。
这就是说前
9
位的比较是完全可
以避免的！我们直接从
S[11]
T
[10]
开始比
较。这时候一比较就发现失配，因此
extend[2]=9
。
以上的例子是有代表性。下面提出一般的算法。
设
extend[1..k]
已经算好，并且在以前
的匹配过程中到达的最远位置是
p
。最
远位置严格的说就是
i+extend[i]-1
的最大值，<
/p>
其中
i=1,2,3,…,k
；
不妨设这个取最
大值的
i
是
a
。
(
下
图黄色表示已经求出来了
extend
的位置
< br>)
S
„„
1
k
k+1
p
根据定义
S[a..p]=T[1..p-a+1]
S[k+1..p]=T[k-a+2..p-a+1]
，令
L=next[k-a+2]
。
有两种情况。<
/p>
第一种情况
k+L
，如下图：
„„
S
1
k
k+1
„„
p
T
„„
1
L
L+1
„„
m
上面的红色部分是相等的。蓝色
部分肯定不相等，否则就违反了“
next[i]
表
示
T[i..m]
与
T<
/p>
的
最长
公共前缀长度”的定义。
（因为
next[k-a+2]=L
，如果蓝色
部
分相等的话，那么就有
next[k-a+2]=L+1
或者更大，矛盾）
。
这时候我们无需任何比较就可以知道
extend[k+1]=L
< br>。
同时
a, p
的值都保持不<
/p>
变，
k
k+1
，继续上述过程。
第二种情况
k+L>=p
。如下图：
S
„„
1
k
k+1
„„
p
p+1
„„
„„
„„
„„
1
L
T
上图的紫色部分是未知的。
因为在计算
extend[1..k]
的时
候，
到达过的最远地
方是
p
，所以
p
以后的位置从未被探访过，我们也就无从
紫色部分是否相等。
这种情况下，就要从
S[p+1]
T[p-k+1]
开始匹配，直到失配为止。匹配完之
后，比较
extend[a
]+a
和
extend[k+1]+(k+1)
的大小，如果后者大，就更新
a
。
整个算法描述结束。
上面的算法为什么是线性的呢？
很容
易看出，在计算的过程中，凡是访问过的点，都不需要重新访问了。一
旦比较，都是比较
以前从不曾探访过的点开始。因此总的时间复杂度是
O(n+m),
是线性的。
还剩下一个问题：
n
ext[]
这个辅助数组怎么计算？复杂度是多少？
我们发现计算
next
实际上以
T
为母串、
T
为子串的一个特
殊
“扩展的
KMP
”
< br>。
用上文介绍的完全相同的算法计算
next
即可。
（用
next
本身
计算
next
，
具体可以
参考标准
KMP
或者作者的程序）此不赘述。
请读者认真领会上面算法的思想，即：已
经访问过的点绝不再访问，充分利
用已经得到的信息。
本文最后还会对此进行一定的总结。
【最长回文子串的分治算法】
问题
1
最长回文子串
顺序和逆序读起来完全
一样的串叫做回文串。比如
acbca
是回文串，而
abc
不是（
abc
的顺
序为“
abc
”
，逆序为“
cba
”
，不相同）
。<
/p>
输入长度为
n
的串
S
，求它最长回文子串。
我们把串分成均匀的两部分：
对左边、右边分别递归求最长回文子串，下面的工作只要考虑
那些“跨越”
粗线的回文串即可。
假设上面是一个回文串，深桔色和深蓝色的部分对称相等。
如上，实际上就是桔色和蓝色对称相等、且浅桔色和浅蓝色对称相等。桔色
< br>和浅桔色交接的地方（也就是粗红线）
，称之为这个回文串的“
< br>对称分界点
”
。
一个回文串必然满足：
1
、对称分界点到二分点（上图两条粗线条之间的部分）之间，是回文。
<
/p>
2
、从对称分界点向左扩展、从二分点向右扩展，必须是完全相等
的。
设原串为
S
，左边的串记为
L
、右边的串记为
R
。字符串
S
的逆序记为
r(S)
。
L
R
用
ex
tend_west[i]
表示第
i
个
字符向左，和
R
匹配，最远可以匹配多远。
i
extend_west[i]=3
显然
extend_west[i]
就是以
r(L)
为母串，
R
为子串的“扩展
KMP
”
。
O(n)
内可
以解决
。
类似的
< br>extend_east[i]
表示从第
i
个字符向右扩展，和
r(L)
匹配，最远可以匹
配多远。
i
extend_east[i]=4
显然
extend_east[i]
是以
L
为母串，
r(L)
为子串的“
扩展
KMP
”
。<
/p>
O(n)
内可以解决
。
< br>
求出来
extend_west
和
extend_east
有什么用呢？
A
M
我们
枚举“对称分界点”
，设为
A
；设二分
点为
M
。根据条件，只要满足：
extend_east[A]*2>=M-A+1
就肯定存
在以
A
为对称分界点的回文串。
S[A
..M]
称为基本回文串。
因为要求
长度最大，我们在基本回文串的基础上向两边扩展，容易发现扩展
的长度就是
extend_west[A-1]
（规定
ext
end_west[0]=0
）
，所以此时的长度：
LENGTH=extend_west[A-1]*2+M-A+1
枚举所有可能的“对称分界点”
（总共不超过
< br>n
个）
，对每个分界点，根据上
面的分析，只要用
O(1)
的时间复杂度就能判定它的合法性、
以及求出以该点为
分界点时的最大回文串长度。
最后取最大值即可。
注意到上面的讨论中，回文串的“重心”在
L
中——
所谓重心就是回文串中
点。所以“对称分界点”也在
L
中。实际上还有可能是下面的情况：
M
A
类似处理即可，此不赘述。
以上我们就在
O(n)
的时间复杂度内（
n=|S|
）
，求出了跨越“二分点”的最长
回文串长度。
分析一下时间复杂度。设计算长度为
n
的串的时间复杂度是
f(n)
，一个
粗略
的递推可以写成：
f(n)=2f(n/2)+n
(
其
中
n
是求跨越二分点的最长回文子串的复杂度，
f(n/2)
分别
是递归处理两边的复杂度
)
f(1)=1
很容易算出：
f(n)~nlogn
也就是说该算法复杂度是
O(nlogn)
。
【最长重复子串的分治算法】
问题
2
最长重复子串
如果一个串
x
在
S
中出现，并且
xx
也在
S
中出现
，那么
x
就叫做
S
的重复
子串。
输入长度为
n
的串
S
，求它的最
长重复子串。
有了最长回文串的解题基础，研究最长重复子串就要简单多了。
我们把串分成均匀的两部分：
对左边、右边分别递归求最长重复
子串，下面的工作只要考虑那些“跨越”
粗线的重复子串即可。
假设深桔色和深蓝色的部分完全相等。
（也就是说存在一个长度为<
/p>
5
的重复
子串）
如上，实际上就是桔色和蓝色相等、且浅桔色和浅蓝色相等。桔色和浅桔色
< br>交接的地方（也就是粗红线）
，称之为这个重复子串的“
重复分界点
”
。
(
重复分
界点到二分点的距离，实际上就是重复子串的长度
)
设原串为
S
，左边的串记为
L
、右边的串记为
R
。字
符串
S
的逆序记为
r(S)
。
L
R
用
extend_east[i]<
/p>
表示第
i
个字符向右，和
R
匹配，最远可以匹配多远。
i
Extend_east[i]=3
显然
extend_east[i]
就是以
L
为母串，
R
为子串的“扩展
KMP
”
。
O(n)
内可以
解
决
。
类似的
extend_west[i]
表示从第
i
个字符向左扩展，和
r(L)
匹配，最远可以匹
配多远。
i
extend_west[i]=4
显然
extend_west[i]
是以
r(L)
为母串，
r(L)
为子串的“扩展
< br>KMP
”
。
O(n)
内可
以解决
。
求出来
extend_west
和
extend_east
有什么用呢？
A
M
我们
枚举“重复分界点”
，设为
A
；设二分
点为
M
。根据条件，只要满足：
extend_east[A]+extend_west[A-1]>=M-A+1