005._longest_palindromic_substring.md

### 5. Longest Palindromic Substring

题目:

https://leetcode.com/problems/longest-palindromic-substring/

难度:

Medium



思路0:

暴力解法绝对不行

思路1:

所以一个好的想法是 s 和 reverse(s) 共有的最长的 substring就是longest palindromic substring -> 问题转成求Longest common substring problem

参见wikipedia

，典型动归

LCSuff(S1...p, T1...q) = LCS(S1...p1, T1...q-1) if S[p] = T[q] else 0



伪码也有了，代码也有：

https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring#Python_2

这样也超时？
```python
    class Solution(object):
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            def lcs(s1, s2):
                m = [[0] * (1 + len(s2)) for i in xrange(1 + len(s1))]
                longest, x_longest = 0, 0
                for x in xrange(1, 1 + len(s1)):
                    for y in xrange(1, 1 + len(s2)):
                        if s1[x - 1] == s2[y - 1]:
                            m[x][y] = m[x - 1][y - 1] + 1
                            if m[x][y] > longest:
                                longest = m[x][y]
                                x_longest = x
                        else:
                            m[x][y] = 0
                return s1[x_longest - longest: x_longest]
    
            return lcs(s, s[::-1])
```
因为以为这样s[::-1]已经很快了.

这个方法是buggy的，看字符串abcxgcba,它reverse之后是abcgxcba,它们有公共字符串，但是这里面没有回文，修复方式是：

we check if the substring’s indices are the same as the reversed substring’s original indices. If it is, then we attempt to update the longest palindrome found so far; if not, we skip this and find the next candidate.

我觉得的修复方式这样么：

    原本     翻转
    ABXYBA   ABYXBA
    
    求出来的substring indices是 0:2 但是这个s1[0:2] 和 s2[0:2]一样，所以不行
    同理common substring indices还是s[4:6] 和s2[4:6]一样，不行
    
    而比如ABAD和 DABA
    
    substring indice 一个是0：3， 一个是1:4，这样就没问题
    



思路2:



依次把每一个字符当做回文字符串的中间字符，找到以该字符为中间字符的回文串的最大长度。分别对奇偶的情况进行讨论，接下来的关键就是对边界的把握，确保下标不要越界。当子串已经包含首字符或最后一个字符且此时还是回文串的时候，下标分别会向两边多移一位，需要补回来。

参考https://shenjie1993.gitbooks.io/leetcode-python/content/005%20Longest%20Palindromic%20Substring.html
```python
    class Solution(object):
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            n = len(s)
    
            # empty or one char
            if n < 2:
                return s
    
            # left index of the target substring
            l = 0
            # right index of the target substring
            r = 0
            # length of the longest palindromic substring for now
            m = 0
            # length of the current substring
            c = 0
    
            # Whether the substring contains the first character or last character and is palindromic
            b = True
            for i in range(n):
                # Odd situation
                for j in range(min(n-i,i+1)):
                    if s[i-j] != s [i+j]:
                        b = False
                        break
                    else:
                        c = 2 * j + 1
    
                if c > m :
                    l = i - j + 1 - b
                    r = i + j + b
                    m = c 
                b = True
    
                # Even situation
                for j in range(min(n - i - 1, i + 1)):
                    if (s[i - j] != s[i + j + 1]):
                        b = False
                        break
                    else:
                        c = 2 * j + 2
                if (c > m):
                    l = i - j + 1 - b
                    r = i + j + 1 + b
                    m = c
                b = True
            return s[l:r]
```
以上是参考版本，自己写的版本：
```python
    class Solution(object):
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            n = len(s)
    
            m,l,r = 0,0,0
    
            for i in range(n):
                # odd case
                for j in range(min(i+1,n-i)):
                    if s[i-j] != s[i+j]:
                        break
                    if 2*j + 1 > m :
                        m = 2 * j + 1
                        l = i-j
                        r = i+j
    
    
                if i+1 < n and s[i] == s[i+1]:
                    for j in range(min(i+1,n-i-1)):
                        if s[i-j] != s[i+j+1]:
                            break
                        if 2 * j + 2 > m :
                            m = 2*j +2
                            l = i-j
                            r = i+j+1
    
    
            return s[l:r+1]
```


思路3:

[Manacher算法](https://www.felix021.com/blog/read.php?2040) 

Manacher算法增加两个辅助变量id和mx，其中id表示最大回文子串中心的位置，mx则为id+P[id]，也就是最大回文子串的边界。得到一个很重要的结论：

- 如果mx > i，那么P[i] >= Min(P[2 * id - i], mx - i) . 为什么这样说呢，下面解释

下面，令j = 2*id - i，也就是说j是i关于id的对称点。

- 当 mx - i > P[j] 的时候，以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中，由于i和j对称，以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中，所以必有P[i] = P[j]；
![](https://github.com/Lisanaaa/myTODOs/blob/master/manacher1.png)

- 当 P[j] >= mx - i 的时候，以S[j]为中心的回文子串不一定完全包含于以S[id]为中心的回文子串中，但是基于对称性可知，下图中两个绿框所包围的部分是相同的，也就是说以S[i]为中心的回文子串，其向右至少会扩张到mx的位置，也就是说 P[i] >= mx - i。至于mx之后的部分是否对称，再具体匹配。
![](https://github.com/Lisanaaa/myTODOs/blob/master/manacher2.png)
所以P[i] >= Min(P[2 * id - i], mx - i)，因为以j为中心的绘回文子串的左边界可能会比mx关于id的对称点要大，此时只能证明P[i]=P[2 * id - i]
- 此外，对于 mx <= i 的情况，因为无法对 P[i]做更多的假设，只能让P[i] = 1，然后再去匹配。

在下面的程序中我的P数组保存的是，以当前字符为回文子串中心时，该回文子串的长度（不包含当前字符自身）


简单地用一个小例子来解释：原字符串为'qacbcaw'，一眼就可以看出来最大回文子串是'acbca'，
下面是我做的图，累shi了！

![](https://github.com/Lisanaaa/myTODOs/blob/master/manacher3.jpg)



所以最终代码中的max_i就是字符'b'所对应的index8，start的值就是(max_i - P[max_i] - 1) / 2 = 1,最终输出结果为s[1:6],即‘acbca’

```python
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        def preProcess(s):
            if not s:
                return ['^', '&']
            T = ['^']
            for i in s:
                T += ['#', i]
            T += ['#', '$']
            return T
        T = preProcess(s)
        P = [0] * len(T)
        id, mx = 0, 0
        for i in range(1, len(T)-1):
            j = 2 * id - i
            if mx > i:
                P[i] = min(P[j], mx-i)
            else:
                P[i]= 0
            while T[i+P[i]+1] == T[i-P[i]-1]:
                P[i] += 1
            if i + P[i] > mx:
                id, mx = i, i + P[i]
        max_i = P.index(max(P))    #保存的是当前最大回文子串中心位置的index
        start = (max_i - P[max_i] - 1) / 2
        res = s[start:start+P[max_i]]
        return res
```
run code的时候结果会跟expected不一样，但是该input确实2个结果都可以，所以放心地submit吧
还可以转到[647题](https://github.com/Lisanaaa/thinking_in_lc/blob/master/647._Palindromic_Substrings.md)去看一看，也可以用这个算法解