Longest Palindromic Substring Length
Python
Hard
2 views
Problem Description
A string s is provided (no spaces). Compute length of longest palindromic substring. Use linear-time method.
Output Format
One integer maxLen.
Official Solution
import sys
s=sys.stdin.read().strip()
if not s: sys.exit(0)
# Manacher
T=['^']
for ch in s:
T.append('#'); T.append(ch)
T.append('#'); T.append('$')
P=[0]*len(T)
C=0
R=0
for i in range(1,len(T)-1):
mir=2*C - i
if i<R:
P[i]=min(R-i,P[mir])
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]
mx=0
for v in P:
if v>mx:
mx=v
sys.stdout.write(str(mx))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!