模板 manacher算法

题目描述

给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.

字符串长度为n

输入输出格式

输入格式：

一行小写英文字符a,b,c...y,z组成的字符串S

输出格式：

一个整数表示答案

输入输出样例

输入样例#1：
复制

aaa

输出样例#1： 复制

3

说明

字符串长度len <= 11000000

http://blog.****.net/dyx404514/article/details/42061017

 #include<iostream>
 #include<cstdio>
 #include<algorithm>
 #include<cstring>
 #include<cmath>
 using namespace std;
 char ch[],s[];
 int len[],n,ans,tot;
 void change()
 {int i,j;
   for (i=;i<n;i++)
     {
       s[++tot]='#';
       s[++tot]=ch[i];
     }
   s[++tot]='#';
   s[++tot]='$';
   n=tot;
 }
 void manacher()
 {int i;
   int mx=,po=;
   for (i=;i<=n;i++)
     {
       if (mx>i)
     len[i]=min(mx-i,len[*po-i]);
       else len[i]=;
       while (s[i-len[i]]==s[i+len[i]]) len[i]++;
       if (len[i]+i>mx)
     {
       po=i;
       mx=len[i]+i;
     }
       ans=max(ans,len[i]-);
     }
 }
 int main()
 {
   scanf("%s",ch);
   n=strlen(ch);
   change();
   manacher();
   cout<<ans;
 }