验证中...
开源中国 2018 年度最后一场技术盛会邀你来约~错过就要等明年啦!点此立即预约
語言: Python
分類: 算法分析
最後更新於 2018-12-09 10:36
gistfile1.txt
原始數據 複製代碼
#最长回文串
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)

評論列表( 0 )

你可以在登錄後,發表評論

搜索幫助