Manacher TLE on #2,悬棺
查看原帖
Manacher TLE on #2,悬棺
788627
Ydoc770楼主2025/7/24 20:45
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e7 + 10;
int n, ans, tot; char s1[maxn], s[maxn << 1];
int d[maxn << 1];

void calc() {s[0] = '~'; for(int i = 1; i <= n; i++) s[++tot] = '#', s[++tot] = s1[i]; s[++tot] = '#';} 
void manacher() {
	for(int i = 1, mid = 0, r = 0; i <= tot; i++) {
		if(i <= r && d[2 * mid - i] < r - i + 1) d[i] = d[2 * mid - i];
		else {
			d[i] = min(1, r - i + 1);}
			while(s[i + d[i]] == s[i - d[i]]) d[i]++;
			if(i + d[i] > r) {
				r = i + d[i] - 1, mid = i;
				if(s[i] == '#') for(int j = d[i] - 1; j >= 2; j -= 2) {//从大到小枚举新增可能的回文串长 
					int lst = i - (j >> 1);//枚举左回文串的中心
					if(lst >= 1 && s[lst] == '#' && lst + d[lst] - 1 >= i) {ans = max(ans, j); break;}//左边是偶回文串且回文半径覆盖枚举的半径 
				}
			}
		
	} return;
}

int main() {
	ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> (s1 + 1); calc(), manacher();
	cout << ans;
	
	return 0;
} 
2025/7/24 20:45
加载中...