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,这是什么原因,求大佬解惑