洛谷-P3805板子题

关键点:

  1. 要有两个字符串，且处理后的字符串长度略大于原串2倍（肯定 &lt; 2 n + 10 &lt;2n+10 <2n+10）
  2. p数组的更新
  3. mid和r的转移 
//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1e4+10;
const int mod = 1e9+7;
const double eps = 1e-9;

char s[25000000], s0[12000000];
int p[25000000];

int change() {
    int len=strlen(s0);
    s[0]='?', s[1]='#';
    int j=2;
    for(int i=0; i<len; ++i) s[j++]=s0[i], s[j++]='#';
    s[j]='!';
    return j;
}

int Manacher() {
    int len=change(), mid=1, r=1, ans=1;
    for(int i=1; i<len; ++i) {
        if(i<r) p[i]=min(r-i,p[mid*2-i]); //如果可以直接利用，那肯定直接用呀
        else p[i]=1; //否则就只能先等于1了
        while(s[i-p[i]]==s[i+p[i]]) p[i]++; //暴力拓宽自身
        if(r<i+p[i]) mid=i, r=i+p[i]; //右边界如果拓宽，则mid也要变化
        ans=max(ans,p[i]-1);
    }
    return ans;
}

int main() {
    //ios::sync_with_stdio(false);
    scanf("%s", s0);
    printf("%d\n", Manacher());
}