验证中...
Languages: Python
Categories: 算法分析
Latest update 2018-12-09 10:36
gistfile1.txt
Raw Copy
#最长回文串
def manacher(s):
assert '$' not in s and '^' not in s and '#' not in s
if s=='':
return (0, 1)
t = '^#' + '#'.join(s) +'#$'
c = 0
d = 0
p = [0] * len(t)
for i in range(1, len(t)-1):
mirror = 2*c -i
p[i] = max(0, min(d - i,p[mirror]))
while t[i+1+p[i]] == t[i-1-p[i]]:
p[i] += 1
if i+p[i]>d:
c = i
d = i+p[i]
(k, i) = max((p[i],i) for i in range(1, len(t)-1))
return ((i-k)//2, (i+k)//2)
if __name__ == '__main__':
s = 'Hello,Hello,olleH,Google,GoogleelgooGelgooG...'
result = manacher(s)
print(result)

Comment list( 0 )

You need to Sign in for post a comment

Help Search