关于马拉车
  • 板块学术版
  • 楼主凤年
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/2/15 15:04
  • 上次更新2023/10/24 00:43:57
查看原帖
关于马拉车
469309
凤年楼主2023/2/15 15:04

rt,这是代码

void manacher() {
	s[0] = s[1] = '#';
	for(int i = 0; i < n; i++) {
		s[i * 2 + 2] = a[i];
		s[i * 2 + 3] = '#';
	}
	n = n * 2 + 2;

	int r = 0, mid;
	for(int i = 1; i < n; i++) {
		if(i < r)                                 // 可以白嫖
			p[i] = min(p[(mid << 1) - i], r - i + 1); // 左侧区间A可能有超过S的部分,所以初始状态最大就是r - i + 1
		else
			p[i] = 1;
		for(;s[i + p[i]] == s[i - p[i]];++p[i])  // 暴力扩展
			if(p[i] + i > r) {                    // 更新r与mid
				r = p[i] + i;
				mid = i;
			}
	}
}

我把 for(;s[i + p[i]] == s[i - p[i]];++p[i]) 换成 while(s[i + p[i]] == s[i - p[i]]) ++p[i]; 100pts -> 52pts,这是什么原因,求大佬解惑

2023/2/15 15:04
加载中...