2016-05-16：资料+最长回文子串
作者:
袁一帆 | 来源:发表于
2016-05-17 00:27 被阅读31次
# 最长回文子串
def manacher(s):
s = '#'+'#'.join(s)+'#'
rl, maxRight,pos,maxLen= [0]*len(s),0,0,0
for i in xrange(len(s)):
if i<maxRight:
rl[i] = min(rl[2*pos-i],maxRight-i)
else:
rl[i]=1
while i-rl[i]>=0 and i-rl[i]<len(s) and s[i-rl[i]]==s[i+rl[i]]:
rl[i]+=1
if rl[i]+i-1>maxRight:
maxRight=rl[i]+i-1
pos=i
maxLen=max(maxLen, rl[i])
return maxLen-1
print manacher('tattarrattat')
本文标题：2016-05-16：资料+最长回文子串
本文链接：https://www.haomeiwen.com/subject/ijjbrttx.html
网友评论