Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Manacher's algorithm solution in Speedy category for The Longest Palindromic by DiZ
def longest_palindromic(s):
# Transform S into T.
# For example, S = "abba", T = "^#a#b#b#a#$".
# ^ and $ signs are sentinels appended to each end to avoid bounds checking
T = '#'.join('^{}$'.format(s))
n = len(T)
P = [0] * n
C = R = 0
for i in range (1, n - 1):
P[i] = R > i and min(R - i, P[2*C - i]) # equals to i' = C - (i-C)
# Attempt to expand palindrome centered at i
while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
P[i] += 1
# If palindrome centered at i expand past R,
# adjust center based on expanded palindrome.
if i + P[i] > R:
C, R = i, i + P[i]
# Find the maximum element in P.
maxLen, centerIndex = max((n, -i) for i, n in enumerate(P))
return s[(-centerIndex - maxLen) // 2: (-centerIndex + maxLen) // 2]
March 3, 2016
Comments: