Manacher——最长回文子串问题

P3805 【模板】Manacher

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define endl '\n'
#define int long long 
const int N=11000002;
string s;
char S[3*N];
int n;
int p[3*N];//p[i]:于i的最大回文半径，包含它自己 
void change(){int k=0;S[k++]='$';S[k++]='#';for(int i=0;i<n;i++){S[k++]=s[i];S[k++]='#';}S[k++]='&';n=k;
}
void solve(){cin>>s;n=s.length();change();int r=0,c=0;for(int i=1;i<n;i++){//从1开始 因为：1.避免越界  2.没必要算0 if(i<r){p[i]=min(p[(c<<1)-i],p[c]+c-i);//其中 因为(i+j)/2=c 所以j=2c-1 }else p[i]=1;while(S[i+p[i]]==S[i-p[i]])p[i]++;if(p[i]-1+i>=r){r=p[i]-1+i;c=i;}}int ans=1;for(int i=1;i<n;i++){ans=max(ans,p[i]);//字符串经过处理，变长了一倍，半径刚好就是原长 }cout<<ans-1<<endl;
}
signed main(){IOSsolve();return 0;
}