Leetcode(5) Longest Palindromic Substring

发表于 | 更新于 | 分类于

Description:

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: “babad” Output: “bab” Note: “aba” is also a valid answer.

Example:

Input: “cbbd” Output: “bb”

解法：

Manacher’s Algorithm 马拉车算法

这个算法是求解回文字符串的常见方法，时间复杂度是O(n)，他的本质是在常规的回文字符串的查找算法上进行优化，利用回文字符串的对称性减少计算时间。下面是算法的主要步骤：

首先，Manacher算法提供了一种巧妙地办法，将长度为奇数的回文串和长度为偶数的回文串一起考虑，具体做法是，在原字符串的每个相邻两个字符中间插入一个分隔符，同时在首尾也要添加一个分隔符，分隔符的要求是不在原串中出现，一般情况下可以用#号。下面举一个例子：

img

Manacher算法用一个辅助数组Len[i]表示以字符T[i]为中心的最长回文字串的最右字符到T[i]的长度，比如以T[i]为中心的最长回文字串是T[l,r],那么Len[i]=r-i+1。

对于上面的例子，可以得出Len[i]数组为:

img

这个数组有一个重要的性质：Len[i]-1就是该回文子串在原字符串S中的长度，证明如下：

首先在转换得到的字符串T中，所有的回文字串的长度都为奇数，那么对于以T[i]为中心的最长回文字串，其长度就为2*Len[i]-1,经过观察可知，T中所有的回文子串，其中分隔符的数量一定比其他字符的数量多1，也就是有Len[i]个分隔符，剩下Len[i]-1个字符来自原字符串，所以该回文串在原字符串中的长度就为Len[i]-1。

故计算Len数组即可求得原字符串中最长回文子串，Len计算过程如下：

从右往左计算Len数组。Manacher算法的优化之处在于利用之前已经求得的Len数组的部分值减少计算新值的循环次数。即：

当计算Len[i]时，Lenj已经计算完毕。设P为之前计算的Len数组中的最大值所对应的右端点（即当前已找到的最长回文子串的右端点），并且设取得这个最大值的位置为po（即Len取得当前已知的最大值的数组序号，即中心点的位置），分两种情况：

第一种情况：i<=P

考虑回文字符串的对称性，找到i相对于po的对称位置，设为j，又分为两种子情况：

1.1 如果Len[j]<P-i，如下图：

img

那么说明以j为中心的回文串一定在以po为中心的回文串的内部，且j和i关于位置po对称，由回文串的定义可知，一个回文串反过来还是一个回文串，所以以i为中心的回文串的长度至少和以j为中心的回文串一样，即Len[i]>=Len[j]。由对称性可知Len[i]=Len[j]。

1.2 如果Len[j]>=P-i，如下图：

img

由对称性，说明以i为中心的回文串可能会延伸到P之外，而大于P的部分我们还没有进行匹配，所以要从P+1位置开始一个一个进行匹配，直到发生失配，从而更新P和对应的po以及Len[i]。

第二种情况：i>P

如果i比P还要大，说明对于中点为i的回文串还一点都没有匹配，这个时候，就只能老老实实地使用常规算法进行一个一个匹配了，匹配完成后要更新P的位置和对应的po以及Len[i]。

总而言之：

计算Len数组时考虑对称性减少匹配次数，新增两个辅助变量mx和id，其中id为当前已知的最大回文子串中心的位置（Len(j)取最大值时的j值），mx是Len取最大值时回文串能延伸到的最右端的位置，这个算法的最核心的一行如下：

1
p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;

我的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        t = "#";
        i = 0
        # 预处理
        while(i<len(s)):
            t+=s[i];
            t+="#";
            i+=1;
        # 计算
        rmax = 0; center = 0; i = 0; rescenter = 0; reslen = 0;p = [0]*len(t);
        while(i<len(t)):
            if(rmax>i):
                x = rmax-i;
                y = p[int(2*center-i)];
                if(x<y):
                    p[i] = x;
                else:
                    p[i] = y;
            else:
               p[i] = 1;
        # 向两边查找对称字符串（常规方法）
            if(i-p[i]>=0 and i+p[i]<len(t)):
                while(t[i+p[i]] == t[i-p[i]]):
                    p[i]+=1;
                    if(i-p[i]<0 or i+p[i]>=len(t)):
                        break;
            if(i+p[i]-1>rmax):
                rmax = i + p[i] - 1;
                center = i;
            if(p[i]>reslen):
                reslen = p[i];
                rescenter = i;
            i+=1;
        r = t[rescenter-reslen+1:rescenter+reslen-1].replace('#','');
        return r;