经典题目 最长回文子串 Longest Palindromic Substring

只想说这个Manacher’s Algorithm简直太牛逼了.

这题题目很经典,最长回文子串

Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

View Code PYTHON
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
class Solution:
    # @return a string
    def longestPalindrome(self, s):
        def preProcess(s):
    	    n = len(s)
    	    if n == 0:
    	    	return "#$"
    	    ret = "^"
    	    for c in s:
    	    	ret += "#" + c
    	    ret += "#$"
    	    return ret
    	t = preProcess(s)
    	P=[0]
    	C,R = 0,0
    	for i in range(1,len(t)-1):
    		i_mirror = 2 * C - i
    		if R > i:
    			P += [min(R-i,P[i_mirror])]
    		else:
    			P += [0]
    		while t[i+1+P[i]] == t[i-1-P[i]]:
    			P[i] += 1
    		if i + P[i] > R:
    			C = i
    			R = i + P[i]
    	maxLen = max(P)
    	index = P.index(maxLen)
    	return s[(index - 1 - maxLen) / 2 : (index - 1 + maxLen) / 2]

 

Share This: 

Leave a Reply

Your email address will not be published. Required fields are marked *