牛客小白月赛13——小A的回文串 解题报告(马拉车算法)

回文串大家都很熟悉，但我们平常使用的方法是枚举中心点向外扩展求，复杂度是.但这道题，需要枚举n种字符串，每个最长为5e3，若找最大长度会炸，所以，需要马拉车算法优化，复杂度为。具体算法内容网上有很多。具体看代码注释吧。

#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset> 
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}

template<typename T> void read(T &x)
{
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int lcm(int a,int b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod 
    ll ans=1;
    while(n){
        if(n&1) ans=((ans%mod)*(a%mod))%mod;
        a=((a%mod)*(a%mod))%mod;
        n>>=1;
    }
    return ans%mod;
}
//==============================================================
const int maxn=5e3+10;
string str;
int p[maxn];
int solve(string pos){
    memset(p,0,sizeof(p));
    //预处理，给回文子串加字符
    string t="$";//开头
    rep(i,0,int(pos.length())-1){
        t+="#";
        t+=+pos[i];
        //cerr<<pos[i]<<" ";
    }
    t+="#";//结尾
    //cerr<<endl;
    //cout<<t<<endl;
    int id=0,mx=0;
    //id为目前能到达的、最右边的、回文子串的重心
    //mx为目前能到达的、最右边的、回文子串的右端点
    int maxlen=-1;
    //回文子串长度
    int n=t.length();
    rep(i,0,n-1){
        p[i]=mx>i?min(p[2*id-i],mx-i):1;
        while(t[i+p[i]]==t[i-p[i]]) p[i]++;
        if(mx<p[i]+i) mx=p[i]+i,id=i;
        if(maxlen<p[i]-1) maxlen=p[i]-1;
    }
    return maxlen;
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    //===========================================================
    IOS;
    cin>>str;
    int ans=0;
    int n=str.length();
    rep(i,1,n){
        ans=max(solve(str),ans);
        char ch=str[0];
        str.erase(str.begin());//修改原字符串
        str+=ch;
    }
    cout<<ans<<endl;
    //===========================================================
    return 0;
}