【模板manacher】

给定一个字符串如abaabacbaaba，求这个字符串中最长的回文串。

奇偶回文优化change

处理回文串的时候，我们知道回文串的长度可能有两种，一种是奇长度，另一个是偶长度。

奇回文： aba 偶回文： aaaa

对于奇长度的回文串，他的中心是一个字符b 对于偶长度的回文串，是没有特定的回文中心的

那么怎么解决这个问题呢？

Solution：字符填充

奇回文： %#a#b#a#& 偶回文： %#a#a#a#a#&

可以发现，奇回文串的中心变成了b，偶回文串的中心变成了#。并且可以发现，他们的向左/右扩展长度就完全等于回文串的长度。

void change(){
  int k=0;
  n=strlen(a);
  s[k++]='$';
  s[k++]='#';
  for(int i=0;i<n;i++)
  {
    s[k++]=a[i];
    s[k++]='#';
  }
  s[k++]='&';
  n=k;
}

暴力优化匹配manacher

一般在解决回文串的时候，我们都是通过暴力拓展第i个位置的字符。那如何优化呢？

考虑到回文串的一个特性， 是一个回文串，意思是，对于与中心点对称的位置，他们在回文的范围内的字符左右一定对称，那么如果我们解决了某一回文串的左端的串的长度，右边的对应位置我们可以直接继承。

如一个字符串为：$acabacabaca$，其中处理的部分为$acabaca$+未处理的部分为$baca$。由于是中心进行拓展的，所以我们知道的信息为$'acab'aca$，那么我们可以把前面的$aca$的数据给依次传递给后续的$aca$,这样做就可以简化。

要是形如aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa这种的字符串，我们的时间就可以大大的缩减。

void manacher(){
  int r=0,c;
  for(int i=0;i<n;i++)
  {
    if( i<r )
      p[i]=min( p[ (c<<1)-i ],p[c]+c-i );
    else p[i]=1;
    while( s[i+p[i]]==s[i-p[i]] ) p[i]++;
    if( i+p[i]>r )
    {
      r=i+p[i];
      c=i;

    }
    ans=max(ans,p[i]);

  }
}

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+1e6+12;
char a[N],s[N<<1];
int n,ans=1,p[N<<1];
void change(){
  int k=0;
  n=strlen(a);
  s[k++]='$';
  s[k++]='#';
  for(int i=0;i<n;i++)
  {
    s[k++]=a[i];
    s[k++]='#';
  }
  s[k++]='&';
  n=k;
}
void manacher(){
  int r=0,c;
  for(int i=0;i<n;i++)
  {
    if( i<r )
      p[i]=min( p[ (c<<1)-i ],p[c]+c-i );
    else p[i]=1;
    while( s[i+p[i]]==s[i-p[i]] ) p[i]++;
    if( i+p[i]>r )
    {
      r=i+p[i];
      c=i;

    }
    ans=max(ans,p[i]);

  }
}
int main(){
  scanf("%s",a);
  change();
  manacher();
  cout<<ans-1;









}