SHARE
TWEET

manachers

a guest Aug 22nd, 2019 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution:
  2.    
  3.     def longestPalindrome(self, s: str) -> str:
  4.        
  5.         n = len(s)
  6.         if n < 1:
  7.             return ''
  8.        
  9.         tmp = list()
  10.         tmp.append('')
  11.         for c in s:
  12.             tmp.append(c)
  13.         tmp.append('')
  14.        
  15.         T = '#'.join(tmp) # 'abc' -> '#a#b#c#'
  16.         N = len(T)
  17.         P = [0] * N
  18.        
  19.         max_rad = 0
  20.         max_rad_ci = 0
  21.        
  22.         C = 0
  23.         R = -1
  24.         for i in range(N):
  25.            
  26.             if i < R:
  27.                 rad = min(P[C*2-i], R-i)
  28.             else:
  29.                 rad = 0
  30.            
  31.             while i-rad >= 0 and i+rad < N and T[i-rad] == T[i+rad]:
  32.                 rad += 1
  33.            
  34.             P[i] = rad
  35.            
  36.             if rad > max_rad:
  37.                 max_rad = rad
  38.                 max_rad_ci = i
  39.            
  40.             if (i + rad - 1) > R:
  41.                 C = i
  42.                 R = i + rad - 1
  43.        
  44.         start = max_rad_ci - max_rad + 1
  45.         end = max_rad_ci + max_rad
  46.         longest_palindrome = T[start:end]
  47.         return longest_palindrome.replace('#', '')
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top