最长回文子串

Python(中心扩展算法)

class Solution:
	def longestPalindrome(self,s):
		if s is None and len(s) < 1:return 0
		start = end = 0
		for i in range(len(s)-1):
			len1 = self.around(s,i,i)
			len2 = self.around(s,i,i+1)
			length = max(len1,len2)
			if length > end-start: 
				start = i-(length-1)//2
				end = i+length//2
		return s[start:end+1] 

	def around(self,s,left,right):
		while 0<=left<=right<len(s) and s[left] == s[right]:
			left -= 1
			right += 1
		return right-left-1

在题解中看见了Manacher 算法，第一次接触这种算法，再看了好久之后还是参考了别人的算法写出了答案。

class Solution:
    def longestPalindrome(self, s):
        s = '$#'+'#'.join(s)+'#'
        n = len(s)
        pos, mx = 0, 1    
        lens = [1]
        for i in range(1, n):
            if mx > i:
                lens.append(min(lens[pos*2-i], mx-i))
            else:
                lens.append(1)
            while i+lens[i]<n and i-lens[i]>0 and s[i+lens[i]]==s[i-lens[i]]:
                lens[i] += 1
            if mx < i+lens[i]:    
                mx = i+lens[i]
                pos = i
        res = ''
        len_max = max(lens)
        pos = lens.index(len_max)
        for i in range(pos-len_max+2, pos+len_max, 2):
            res += s[i]
        return res