题目：Longest Palindromic Substring
题目简述
找出最长回文子串，如输入"babad"，结果为"bab"或"aba"。
马拉车算法
引入
可以观察到回文串根据中心对称，反之可以从中心向两边扩张去寻找最大回文串。一共有2n+1个中心，每个都尝试一下便可以得出答案。为了操作方便，添加分隔符#。
如：babaabac——> #b#a#b#a#a#b#a#c
T为加分割符后的字符串，L[i]代表以T[i]为中心的最长回文子串的长度。最后找出最大的L为13，（13-1）/2后为原字符串的最长回文子串的长度。
上述算法时间复杂度为O(n2）,在具体求解每个L[i]时都需要O(n)的时间复杂度，有没有办法可以提高效率呢？
若从左向右遍历求解，回文串的特性可以发挥一定作用。设L[0]-L[8]已求出，且已经得知T[8]为中心,左边界为T[2],右边界为T[14]是回文串。那么接下来L[9]=L[7]=3,L[10]=L[6]=1,.....，但注意L[3]!=L[13]。具体分析看下文。
根据回文特性简化
若前面已经求出了以C为中心，R为右边界的某个回文串，现在正要求的以i为中心的最大回文串长度。若i<=R，则可以根据对称规则求解，若i>R则只能蛮力求解。
设P为回文半径，即表示以字符T[i]为中心的最长回文字串的最端右字符到T[i]的长度。注：P[i]-1 即为原回文子串的长度
四种情况
i>R
T[i-1]与T[i+1]匹配...T[i-2]与T[i+2]匹配...直至超出字符串边界，或T[i-k]!=T[i+k]i<=R且i+(P[i']-1)<R
P[i] = P[i']-
i<=R且i+(P[i']-1)>R
P[i] = R-i+1
例:如下图，由于T[15]!=T[11]回文串被截断
截断.jpg
有没有可能T[15]==T[11]呢？
若T[15]=T[11]（已知T[11]=T[5]=T[1]），则T[1]=T[15]，P[8]=7+1与P[8]=7矛盾，所以T[15]不可能等于T[11]。因此一定会被截断。 i<=R且i+(P[i']-1)=R
P[i]>=R-i+1
首先，P[i]至少可以是R-i+1，后面可能会有其他的字符使得回文子串继续加长，但也可能没有。具体有没有需要再一一匹配，但匹配的基础是R-i+1。T[i-(R-i+1)]与T[(i+(R-i+1)]匹配..T[i-(R-i+2)]与T[(i+(R-i+2)]匹配...
Python代码
class Solution:
def longestPalindrome(self, s: str) -> str:
c = 0
r = -1
T = '#' + '#'.join(s) + '#'
P = [1]*(len(T))
max_index = 0
for i in range(len(T)):
if i<= r:
P[i] = min(r-i+1,P[2*c-i])
# Try to extend
while i-P[i]>=0 and i+P[i]<len(T) and T[i+P[i]]==T[i-P[i]]:
P[i] += 1
# 循环中顺便找出最长回文子串的中心
if P[i]>P[max_index]:
max_index = i
if i+P[i]-1 >r:
c = i
r = i+P[i]-1
#根据映射关系返回原子串
return(s[(max_index-P[max_index]+2)//2:(max_index+P[max_index]-2)//2+1])
if __name__ == "__main__":
l = 'babad'
t = Solution()
r = t.longestPalindrome(l)
print(r)
总结
- 通过加分割符的方法，使每个中心位置都可以取到，也使字符串长度统一为奇数
- 马拉车算法主要运用的是回文串的特性
