# abacabcaba -> ^#a#b#a#c#a#b#c#a#b#a#$
# r:最右邊回文邊界，c：最長(zhǎng)回文中心
def manacher(_s):
s = '#'.join('^{}$'.format(_s))
c,r,n = 0,0,len(s)
p = n*[0]
for i in xrange(1,n-1):
if r<i:p[i]=0 #超過(guò)最右邊際則初始化為0
else:p[i]=min(r-i,p[2*c-i]) #由回文的對(duì)稱性，未超過(guò)最右邊界的時(shí)候，可以找到當(dāng)前最大回文
while s[i+1+p[i]] == s[i-1-p[i]]: #以當(dāng)前i為中心少漆，向左右尋找回文
p[i]+=1
if i+p[i]>r: #更新最右邊界和最長(zhǎng)回文中心
c,r = i,p[i]+i
maxl,maxi = max((n,i) for i,n in enumerate(p)) #找到最大回文中心的長(zhǎng)度
return _s[(maxi-maxl)/2:(maxi+maxl)/2]
print manacher('abacabcaba')
