AcWing 139. 回文子串的最大长度
原题链接
中等
作者:
姜逍遥
,
2021-06-23 12:45:02
,
所有人可见
,
阅读 242
#include <iostream>
#include <cstring>
using namespace std;
const int N = 2e7 + 10;
int n;
char a[N], b[N];
int p[N];
void init(){
int idx = 0;
b[idx++] = '$', b[idx++] = '#';
for(int i = 0; i < n; i++) {
b[idx++] = a[i];
b[idx++] = '#';
}
b[idx ++] = '^';
n = idx;
}
int manacher(){
int res = 0;
int mr = 0, mid = 0;
for(int i = 1; i < n; i++){
if(i < mr) p[i] = min(p[mid * 2 - 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;
}
}
for(int i = 0; i < n; i++) res = max(res, p[i]);
return res - 1;
}
int main(){
int T = 1;
while ( scanf( "%s",a), strcmp(a, "END")) {
n = strlen(a);
init();
cout << "Case " << T++ << ": " << manacher() << endl;
}
return 0;
}