小A非常喜欢回文串，当然我们都知道回文串这种情况是非常特殊的。所以小A只想知道给定的一个字符串的最大回文子串是多少，但是小A对这个结果并不是非常满意。现在小A可以对这个字符串做一些改动，他可以把这个字符串最前面的某一段连续的字符(不改变顺序)移动到原先字符串的末尾。那么请问小A通过这样的操作之后(也可以选择不移动)能够得到最大回文子串的长度是多少。

一行一个字符串表示给定的字符串S一行一个字符串表示给定的字符串S

一行输出一个整数，表示通过这样的操作后可以得到最大回文子串的长度。

N表示字符串的长度，1≤N≤5000

解题思路：Manacher板子题，每次修改字符串后跑一遍Manacher即可，时间复杂度为O（N^2）
既然说到了Manacher，那就简答讲一下吧，至于详细的讲解过程，可以参考这篇博客：Manacher。
回文字符串可能出现两种情况，一种是长度为奇数的，另一种为长度为偶数的，为了方便，我们可以对字符串进行处理，把它变成一个长度为奇数的字符串。比如字符串：acbbca，可以变成#a#c#b#b#c#a#（注意也可以加入其它字符，但加入的字符不能原字符串出现过的）
，为了防止匹配的时候出现越界的情况，还可以在字符串的最前面加入一个$字符（字符串中为出现过），这里，还需要定义一个数组P[],记录某回文字串的半径，就如$#a#c#b#b#c#a#,第8个字符#的p值为：7,它的坐标为7，此时回文串的长度为7-1=6，回文串的
起始位置为（7-7）/2=0，即坐标减去p的值然后除以二（相当于原字符串acbbca），此时我们可以得到此时的回文字串为acbbca。（想看推导过程可以参考上面推荐的那篇博客QAQ。。）、
这里插上此题的AC代码吧

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<vector>

#include<stack>

#include<cstdio>

#include<map>

#include<set>

#include<string>

#include<queue>

using namespace std;

#define inf 0x3f3f3f3f

#define ri register int

typedef long long ll;

inline ll gcd(ll i,ll j){

    return j==0?i:gcd(j,i%j);

}

inline ll lcm(ll i,ll j){

    return i/gcd(i,j)*j;

}

inline void output(int x){

    if(x==0){putchar(48);return;}

    int len=0,dg[20];

    while(x>0){dg[++len]=x%10;x/=10;}

    for(int i=len;i>=1;i--)putchar(dg[i]+48);

}

inline void read(int &x){

    char ch=x=0;

    int f=1;

    while(!isdigit(ch)){

        ch=getchar();

        if(ch=='-'){

            f=-1;

        }

    }

    while(isdigit(ch))

        x=x*10+ch-'0',ch=getchar();

        x=x*f;

}

const int maxn=1e5+5;

void change(char * c,char * d){

    int len=strlen(c);

    d[0]='(';

    int j=1;

    for(int i=0;i<len;i++){

        d[j++]='#';

        d[j++]=c[i];

    }

    d[j]='#';

    d[j+1]='\0';

  //  puts(d);

}

int manacher(char * c,char * d,int * p){

    change(c,d);

    int ans=-1;

    int len=strlen(d);

    int mx=0,id=0;//mx为回文串最右端，id为中心

    for (int i = 1; i < len; i++)

    {

        if (i < mx)

            p[i] = min(p[2 * id - i], mx - i);//这里是Manacher算法的核心

        else

            p[i] = 1;

        while (d[i - p[i]] == d[i + p[i]])

            p[i]++;

        if (mx < i + p[i])

        {

            id = i;

            mx = i + p[i];

        }

        ans=max(ans,p[i]-1);

    }

    return ans;

}

char ch[maxn*2+5];

char ch1[maxn];

int p[maxn*2+5];

int main(){

    scanf("%s",ch1);

    int ans=0;

    int len=strlen(ch1);

    for(int i=0;i<len;i++){

        ans=max(manacher(ch1+i,ch,p),ans);

    //  cout<<ans<<endl;

        ch1[i+len]=ch1[i];

    }

    cout<<ans;

    return 0;

}