# 005 longest palindromic substring

### 5. Longest Palindromic Substring

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

Medium

，典型动归

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

    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])


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 indice 一个是0：3， 一个是1:4，这样就没问题


    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]


    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]


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

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

• 当 mx - i > P[j] 的时候，以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中，由于i和j对称，以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中，所以必有P[i] = P[j]；

• 当 P[j] >= mx - i 的时候，以S[j]为中心的回文子串不一定完全包含于以S[id]为中心的回文子串中，但是基于对称性可知，下图中两个绿框所包围的部分是相同的，也就是说以S[i]为中心的回文子串，其向右至少会扩张到mx的位置，也就是说 P[i] >= mx - i。至于mx之后的部分是否对称，再具体匹配。 所以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，然后再去匹配。

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题去看一看，也可以用这个算法解

apachecn/AiLearning