最长回文子串
题目
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
示例1:
1 | 输入: "babad" |
示例2:
1 | 输入: "cbbd" |
方法一 - 中心扩展算法
事实上,只需使用恒定的空间,我们就可以在 \( O(n^2) \) 的时间内解决这个问题。
我们观察到回文中心的两侧互为镜像。因此,回文可以从它的中心展开,并且只有 \( 2n - 1 \)个这样的中心 [其中自身\( n \)个,间隙\( n-1 \)个,故可能的中心有\( 2n-1\)个]。
1 | int expandAroundCenter(string s, int left, int right) |
时间复杂度:\( O(n^2)\),由于围绕中心来扩展回文会耗去 \( O(n)\) 的时间,所以总的复杂度为 \( O(n^2)\)。
空间复杂度:\( O(1) \)。
方法二 - Manacher算法
首先通过在每个字符的两边都插入一个特殊的符号,将所有可能的奇数或偶数长度的回文子串都转换成了奇数长度。
比如 abba
变成 #a#b#b#a#
, aba
变成 #a#b#a#
。
此外,为了进一步减少编码的复杂度,可以在字符串的开始加入另一个特殊字符,这样就不用特殊处理越界问题,比如$#a#b#a#
。
以字符串12212321
为例,插入#
和这两个特殊符号,变成了T[]=#1#2#2#1#2#3#2#1#
,然后用一个数组 P[i]
来记录以字符 T[i]
为中心的最长回文子串向左或向右扩张的长度(包括T[i]
,半径长度)。
比如T和P的对应关系:
- T # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 #
- P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1
可以看出,P[i]-1
正好是原字符串中最长回文串的总长度,为5
。
接下来怎么计算 P[i]
呢?Manacher算法增加两个辅助变量C
和R
,其中C
表示最大回文子串中心的位置,R
则为C+P[C]
,也就是最大回文子串的边界。得到一个很重要的结论:
- 如果
R > i
,那么P[i] >= Min(P[2 * C - i], R - i)
下面详细说明这个结论怎么来的
当 R - i > P[j]
的时候,以T[j]
为中心的回文子串包含在以T[C]
为中心的回文子串中,由于 i
和 j
对称,以T[i]
为中心的回文子串必然包含在以T[C]
为中心的回文子串中,所以必有 P[i] = P[j]
,见下图。
当 R - i <= P[j]
的时候,以T[j]
为中心的回文子串不一定完全包含于以T[id]
为中心的回文子串中,但是基于对称性可知,下图中两个绿框所包围的部分是相同的,也就是说以T[i]
为中心的回文子串,其向右至少会扩张到R
的位置,也就是说 R - i <= P[i]
。至于R
之后的部分是否对称,就只能老老实实去匹配了。
对于 R <= i
的情况,无法对 P[i]
做更多的假设,只能P[i] = 1
,然后再去匹配了。
1 | string preProcess(string s) |
时间复杂度:\( O(n) \)。
空间复杂度:\( O(n) \)。
参考
>