题面
题解
我们用mancher算法,可以在O(n) 求出一个串的最大回文串
- 我们要将题中给定的串变为奇数串,比如abaca 就会变成 $#a#b#a#c#a^
- 用一个p[i] 数组表示以si为中心的最大回文串的半径,那么最后求一个最大的半径-1,就是所求结果
- 我们在计算p[i] 的时候枚举维护一个右端点最大的回文串,mr即为右端点,mid为这个回文串的中点
情况1 :当枚举的si在回文串内,以si为中心的回文串在维护的回文串内部,那么它的长度就和p[j] 的长度一样
情况2 :当以i的回文串长度超出维护回文串的范围 ,在这个维护的区间内最大就是mr-i,因为区间a=b ,b=c ,c=d ,如果再大,就会超出维护的范围
情况3 : 如果 si 在mr 的 右边 p[i] =1
- 因为要求最大,我们现在只求出下界,所以while (b[i - p[i]] == b[i + p[i]]) p[i]++;
- 更新mr和mid
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e7 + 10;
int n;
char a[N], b[N];
int p[N]; //以si为中心的最大回文串的半径
//将串变为奇数串
void init() {
int k = 0;
b[k++] = '$', b[k++] = '#';
for (int i = 0; i < n; i++) b[k++] = a[i], b[k++] = '#';
b[k++] = '^';
n = k;
}
int manacher() {
init();
int mr = 0, mid;
for (int i = 1; i < n; i++) {
if (i < mr) p[i] = min(p[2 * mid - i], mr - i);
else p[i] = 1;
while (b[i - p[i]] == b[i + p[i]]) p[i]++;
if (i + p[i] > mr) {
mr = i + p[i];
mid = i;
}
}
int res = 0;
for (int i = 0; i < n; i++) res = max(res, p[i]);
return res-1;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cin >> a;
n = strlen(a);
cout << manacher() << endl;
return 0;
}