LeetCode算法题5:最长回文子串解析
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2:
输入: "cbbd"
输出: "bb"
这个题可以暴力法搜寻,设置一个数组,保存每个位置字符为中心的回文字符串长度,最后输出最长的,但是这样的时间复杂度是O(n^2),有一种专门用来搜寻最长回文子串的快速算法叫Manacher算法,其复杂度是线性的。
算法的思路如下:(来自百度百科)
Manacher算法提供了一种巧妙的办法,将长度为奇数的回文串和长度为偶数的回文串一起考虑,具体做法是,在原字符串的每个相邻两个字符中间插入一个分隔符,同时在首尾也要添加一个分隔符,分隔符的要求是不在原串中出现,一般情况下可以用#号。
辅助数组:
Manacher算法用一个辅助数组Len[i]表示以字符T[i]为中心的最长回文字串的最右字符到T[i]的长度,比如以T[i]为中心的最长回文字串是T[l,r],那么Len[i]=r-i+1。如下图:
Len 数组有一个性质,那就是Len[i]-1就是该回文子串在原字符串S中的长度。
Len数组的计算:
首先从左往右依次计算Len[i],当计算Len[i]时,Len[j] (0<=j<i)已经计算完毕。设P为之前计算中最长回文子串的右端点的最大值,并且设取得这个最大值的位置为po,分两种情况:
第一种情况:i<P
那么找到i相对于po的对称位置,设为j,那么如果Len[j]<P-i,如下图:
那么说明以j为中心的回文串一定在以po为中心的回文串的内部,且j和i关于位置po对称,由回文串的定义可知,一个回文串反过来还是一个回文串,所以以i 为中心的回文串的长度至少和以j为中心的回文串一样,即Len[i]>=Len[j]。因为Len[j]<P-i,所以说i+Len[j]<P。由对称性可知Len[i]=Len[j]。
如果Len[j]>=P-i,由对称性,说明以i为中心的回文串可能会延伸到P之外,而大于P的部分我们还没有进行匹配,所以要从P+1位置开始一个一个进行匹配,直到发生失配,从而更新P和对应的po以及Len[i]。
所以其实Len[i]取的是Len[j]与P-i的最小值。
第二种情况:i>=P
如果i比P还要大,说明对于中点为i的回文串还一点都没有匹配,这个时候,就只能老老实实地一个一个匹配了,匹配完成后要更新P的位置和对应的po以及Len[i]。
所以思路也就是这样了,程序也就出来了。
C++源代码:
class Solution {
public:
string longestPalindrome(string s) {
string T = "*#";
for(int i=0;i<s.length();i++)
{
T += s[i];
T += "#";
}
int maxLen = 0, maxn = 0;
int P = 0;
int po = 0;
int p[T.length()] = {0};
for(int i=0;i<T.length();i++)
{
if(P>i)
p[i] = min(p[2*po-i], P-i);
else
p[i] = 1;
while(T[i-p[i]]==T[i+p[i]])
p[i]++;
if(p[i]+i>P)
{
P = p[i]+i;
po = i;
}
if(maxLen<p[i])
{
maxLen = p[i];
maxn = i;
}
}
return s.substr((maxn-maxLen)/2, maxLen-1);
}
};
python3源代码:
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
T = "*#"
for i in range(len(s)):
T += s[i]
T += "#"
T += "$"
po = 0
maxLen = 0
maxn = 0
p = [0]*len(T)
for i in range(2, len(T)-1):
if p[po]+po>i:
p[i] = min(p[po*2-i], p[po]+po-i)
else:
p[i] = 1
while T[i-p[i]]==T[i+p[i]]:
p[i] += 1
if p[i]+i>p[po]+po:
po = i
if p[po]>maxLen:
maxLen = p[po]
maxn = po
return s[(maxn-maxLen)//2:(maxn-maxLen)//2+maxLen-1]