note: This article comes from the Internet. Please contact me via lethic@163.com if there is any infringement.
lethic@163.com.

manacher,.
,.
manacher,manacher,,,O(n).
,+kmp,.
?

:
,s,rad[i]i,rad[i],:
s[i-rad[i],i-1]=s[i+1,i+rad[i]]
,rad,.
,.
rad[1..i-1],rad,,iradj.j,rad[i].k,1rad[i],[i+1,i+rad[i]]rad.
,,.
rad[k],.3:

rad[i]-k<rad[i-k]
,rad[i-k].,,rad[i+k]rad[i]-k,.?.,,,,rad[i+k]=rad[i]-k.,rad[i+k]=rad[i]-k=min(rad[i]-k,rad[i-k]).

rad[i]-k>rad[i-k]
,rad[i-k].,,,:rad[i+k]=rad[i-k].,rad[i+k]=rad[i-k]=min(rad[i]-k,rad[i-k]).

,:rad[i]-k!=rad[i-k],rad[i+k]=min(rad[i]-k,rad[i-k]).
:rad[i]-k==rad[i-k],,:

,,,,,,,,,ii+k,j=rad[i-k](radrad[i-k]),.
.
O(n),,..
,,.?,(,rad).,.,.:aabbaca,a#a#b#b#a#c#a,,,.
:
fin>>ST;
for (int i=0,End=ST.size(); i!=End; i++)
{
s[(i<<1)+1]=ST[i];
s[(i<<1)+2]=’#’;
}
s[0]=’?’;
s[ST.size()<<1]=’*’;//,
//
for (int i=1,j=0,k,End=ST.size()< {
while (s[i-j-1]==s[i+j+1]) j++; //rad
rad[i]=j;
for (k=1; k i+=k; //irad
j=max(j-k,0); //rad
}
!ural1297(),AC.