题解
细节
所有字符的回文半径初始化为 1
rmax=1
ans=1
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
void solve()
{
string s;
cin>>s;
string s1;
for(int i=0;s[i];i++)
{
s1+='#';
s1+=s[i];
}
s1+='#';
ll n=s1.size();
vector<ll> r(n+5,1);
ll rmax=0;//和自己匹配肯定是回文串
ll ans=1,center=0;
for(int i=0;i<n;i++)
{
if(i<rmax) r[i]=min(rmax-i,r[2LL*center-i]);
while( i-r[i]>=0 && i+r[i]<n &&s1[i+r[i]]==s1[i-r[i]] ) r[i]++;
if(i+r[i]>rmax)
{
center=i;
rmax=i+r[i];
}
if(s1[i]=='#')
{
ans=max(ans,r[i]-1);
}
else
{
ans=max(ans,(r[i]-1)/2*2LL+1);
}
}
cout<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
return 0;
}
标签:int,manacher,s1,rmax,long,ans,P3805,ll,模板
From: https://www.cnblogs.com/pure4knowledge/p/18313048