基准时间限制：1

 秒 空间限制：131072

 KB 分值:

 0

 

 收藏

 关注

回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。

输入一个字符串Str，输出Str里最长回文子串的长度。

　

Input

输入Str（Str的长度 <= 100000)

Output

输出最长回文子串的长度L。

Input示例

daabaac

Output示例

5

相关问题

最长回文子串

 

0

 

回文串划分 V2

 

640

 

回文串划分

 

40

 

回文字符串

 

10

 

//O(n) manacher算法 #include
     
      #include
      
       #include
       
        using namespace std;const int N=1e6+5;int l,len,p[N<<1];char s[N],S[N<<1];void manacher(){    int ans=0,id=0,mx=-1;    for(int i=1;i
        
         i) p[i]=min(p[id*2-i],id+mx-i);        while(i-p[i]-1>=0&&i+p[i]+1<=l&&S[i-p[i]-1]==S[i+p[i]+1]) p[i]++;        if(id+mx
        
       
      
     

 

//O(nlogn) 字符串哈希#include
     
      #include
      
       #include
       
        using namespace std;typedef int i64;const int N=1e6+5;int n,m,ans,a[N];char s[N];i64 P,pow[N],hash_l[N],hash_r[N];void get_hash(){    pow[0]=1;    for(int i=1;i<=m;i++) pow[i]=pow[i-1]*P;    for(int i=1;i<=m;i++) hash_r[i]=hash_r[i-1]*P+a[i];    for(int i=m;i>=1;i--) hash_l[i]=hash_l[i+1]*P+a[i];    }int main(){    P=29;    scanf("%s",s+1);    n=strlen(s+1);    for(int i=1;i<=n;i++){        a[++m]='#';        a[++m]=s[i]-'A';    }    a[++m]='#';    get_hash();    int l,r,mid;    for(int i=1;i<=m;i++){        l=0;        if(i-1
        
         1){            mid=l+r>>1;            i64 hash_to_l=hash_r[i-1]-hash_r[i-mid-1]*pow[mid];            i64 hash_to_r=hash_l[i+1]-hash_l[i+mid+1]*pow[mid];            if(hash_to_l==hash_to_r) l=mid;            else r=mid;        }        ans=max(ans,l);    }    printf("%d",ans);    return 0;}