MnZn刚学Manacher 8pts求助,悬1关
查看原帖
MnZn刚学Manacher 8pts求助,悬1关
759274
Stevehim楼主2023/8/10 18:39

rt

#include <bits/stdc++.h>
#define maxn 11000000
using namespace std;
char s[maxn];
char t[maxn * 2 + 1]; //增加分隔符后的子串
int l[maxn * 2 + 1]; // l表示某个点的当前边界
int n;
int ma = 0;
void manacher(){
	t[0] = '^';
	t[1] = '|';
	for(int i = 1;  i <= n;i++){ //改变原串
		t[2 * i] = s[i];
		t[2 * i + 1] = '|';
	}
	n = n * 2 + 1;
	for(int i = 1,r = -1,c = 0;i <= n; i++){
		l[i] = (i <= r ? min(l[2 * c - i],r - i) : 1);
		while(i - l[i] >= 1 && i + l[i] <= n && t[i + l[i]] == t[i - l[i]]){
			l[i]++;
		}
		if(i + l[i] - 1 > r){
			c = i; //切换原点,因为半径更大了
			r = i + l[i] - 1;
			ma = max((int)floor(r / 2),ma);
		}
	}
}

int main(){
	scanf("%s",s + 1);
	n = strlen(s + 1);
	manacher();
//	for(int i = 1; i <= n; i++){
//		ma = max(l[i],ma);
//	}
	cout << ma;
	return 0;
}
2023/8/10 18:39
加载中...