manacher算法模板
作者:
Heng
,
2020-04-20 02:02:05
,
所有人可见
,
阅读 644
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5;
char s[N], str[N];
int len1, len2, id, mx, ans, p[N];
void init() { // 翻倍
str[0] = '$';
str[1] = '#';
for(int i = 0; i < len1; i++) {
str[i*2+2] = s[i];
str[i*2+3] = '#';
}
len2 = len1 * 2 + 2;
str[len2] = '*';
}
void manacher() {
id = 0, mx = 0;
for(int i = 1; i < len2; i++) {
if(i < mx) p[i] = min(p[2*id-i], mx - i); // 对称点的回文半径 和 i到mx之间的距离
else p[i] = 1;
while(str[i+p[i]] == str[i-p[i]]) p[i]++; // 暴力匹配
if(i + p[i] < mx) { // 更新id和mx
mx = i;
mx = i + p[i];
}
}
}
int main() {
cin >> s;
len1 = strlen(s);
init();
manacher();
for(int i = 0; i < len2; i++) ans = max(ans, p[i]);
cout << ans - 1 << endl;
return 0;
}