https://www.luogu.com.cn/problem/P3805
Orz最后一天学的最多。
#include <bits/stdc++.h>
using namespace std;
string s,ss,z="###";
int n,dp[22451419],m;
int main()
{
cin>>s;
n=s.size();
ss=s+s+z;
ss[m++]='$';
for(int i=0;i<n;i++) {
ss[m++]='#';
ss[m++]=s[i];
}
ss[m++]='#';ss[m]='?';
//cout<<ss;
int max1=0,p;
for(int i=1;i<m;i++) {
if(max1>i)
dp[i]=min(max1-i,dp[2*p-i]);
else
dp[i]=1;
while(ss[i-dp[i]]==ss[i+dp[i]]) dp[i]++;
if(i+dp[i]>max1)
max1=i+dp[p=i];
}
int ans=0;
for(int i=1;i<m;i++)
ans=max(ans,dp[i]-1);
cout<<ans;
return 0;
}