Manacher !!!
Manacher的算法过程就不细讲了，这个很简单。
注意一点性质 ： 一个串本质不同的回文子串个数为O(N)个。
因为只有在mx(最右的能延伸到的点)向右扩展时，才会产生新的回文子串，否则一定在对称的位置出现过。
这样的话，我们便可以找出所有本质不同的回文子串。
然后说一说实现。
众所周知的，Manacher之烂大街实现方法 --- 相邻点间加上符号'#'，首尾加上不同的特殊符号，这样便可将奇偶结合起来。
我的代码：
void manacher(){ //没有写插入特殊字符
int mx=0 , id;
for(int i=1;i<=m;++i){ //m为添加字符后的串长
if(mx>=i) pal[i]=min(mx-i+1,pal[2*id-i]) ;
else pal[i]=1 ;
while(s[i-pal[i]]==s[i+pal[i]]) ++pal[i] ;
if(i+pal[i]-1>mx) {
mx=i+pal[i]-1 , id=i ;
}
}
}
如下(代码粘自黄学长)：
(update:该代码不太好，可以看自己之前的代码)
void manacher()
{
m=2*n+1;
for(int i=1;i<=n;i++) //添加特殊字符
{
a[i<<1]=ch[i];
a[i<<1|1]='#';
}
a[0]='+';a[1]='#';a[m+1]='-';
int mx=0,id;
for(int i=1;i<=m;i++) //主过程
{
if(mx>i)p[i]=min(mx-i,p[2*id-i]);
else p[i]=1; //这一步可能找到新回文串
for(;a[i-p[i]]==a[i+p[i]];p[i]++); //还有这一步，因为一旦扩展，mx也会扩展
if(p[i]+i>mx)mx=p[i]+i,id=i;
}
}
但是 ！！ 这对于有些题来说会特别烦 ！ 对于这些题，我们便可以直接分奇偶回文，做两遍即可。
如下(代码仍然粘自黄学长):
void manacher()
{
int mx=0,id;
for(int i=1;i<=n;i++)
{
if(mx>i)p[i]=min(mx-i,p[2*id-i-1]);
else p[i]=0;
while(ch[i+p[i]+1]==ch[i-p[i]])
{
p[i]++;
}
if(p[i]+i>mx)mx=p[i]+i,id=i;
}
mx=0;
for(int i=1;i<=n;i++)
{
if(mx>i)p[i]=min(mx-i-1,p[2*id-i]);
else {p[i]=1;}
while(ch[i+p[i]]==ch[i-p[i]])
{
p[i]++;
}
if(p[i]+i>mx)mx=p[i]+i,id=i;
}
}
评论