【Manacher】洛谷 P3805 【模板】manacher算法

题链

OI-wiki

字符串以 1 为开头写的

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ll long long
#define ULL unsigned long long
#define Pair pair<LL,LL>
#define ls rt<<1
#define rs rt<<1|1
#define Pi acos(-1.0)
#define eps 1e-6
#define DBINF 1e100
#define mod 998244353
#define MAXN 1e18
#define MS 22000009 

int n,m;
int mnc[MS];
char t[MS];
char s[MS];
int tot,hs; 

int main() {
	ios::sync_with_stdio(false);
	cin >> t+1;
	int h = strlen(t+1);
	for(int i=1;i<=h;i++){ // 预处理原串 
		s[++tot] = 0;
		s[++tot] = t[i];
	}
	s[++tot] = 0;
	
	for(int i=1,l=1,r=0;i<=tot;i++){ // manacher 
		int cc = i > r? 1 : min(mnc[l+(r-i)] , r-i);
		while(1<=i-cc && i+cc<=tot && s[i-cc] == s[i+cc]) cc++;
		mnc[i] = --cc; // mnc[i]表示s[i]这个点向右最多能扩充几个 
		if(i+cc > r){
			r = i+cc;
			l = i-cc;
		}
	} 
	int ans = 1;
	for(int i=1;i<=tot;i++){
		ans = max(ans,mnc[i]);
	}
	cout << ans << "\n";
	
	return 0;
}