200字
「模板」Manacher
2025-11-01
2025-11-01

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;
}