柒葉灬 的博客

柒葉灬 的博客

manacher

posted on 2019-09-26 10:56:17 | under 算法学习 |

manacher

求最长的回文子串。

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
#define debug2(a,x) cerr<<#a<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=1.1e7+100;
bool cur1;
int n;
char str[maxn<<1];
int len[maxn<<1];
bool cur2;
int main(){
//  double Sz=&cur1-&cur2;
//  cout<<Sz/1024<<"KB "<<Sz/1024/1024<<"MB"<<endl<<endl;
//  freopen("data.in","r",stdin);
//  freopen("my.out","w",stdout);
    scanf("%s",str+1);
    n=strlen(str+1)*2+1;
    for(int i=n-1;i>=2;i-=2)
        str[i]=str[i>>1];
    str[0]='$';
    for(int i=1;i<=n;i+=2)
        str[i]='#';
    int mid=0,right=0,mxlen=0;
    for(int i=1;i<=n;i++){
        len[i]=(i<=right?min(len[2*mid-i],right-i+1):1);
        while(str[i+len[i]]==str[i-len[i]])len[i]++;
        if(i+len[i]>right)mid=i,right=i+len[i]-1;
        mxlen=max(mxlen,len[i]);
    }
    cout<<mxlen-1<<endl;
    return 0;
}

可以看出,本质不同的回文子串个数是 $O(n)$ 级别的。

求回文子串个数只需要枚举中点即可