- 分享
manacher
- @ 2025-10-19 15:04:14
/*
预处理:
回文串长度个数为奇数,则其对称位置在某个字符。
否则在两个字符中间,非常不利于计算回文串长度。
处理方法:在字符串的两边加上#,任意两个字符之间加上#
字符串的长度 = len*2 + 1 (#个数始终比原字符个数多1)
str: aba => #a#b#a#
p[i] : 以s[i]为中心的最大回文串的半径长度
#a#b#a#
1214121
转化之后: x长度的回文串转化后得到回文串半径为x+1
求p[i]: 从前往后遍历,同时维护一个右边界最靠右的回文串
记录其mid 和max - right,递推到i时,找i关于mid的对称点j = 2mid - i
1.若i在(mid, mr):
(1) j - p[j] > ml => p[i] = p[j]
(2) j - p[j] <= ml => p[i] = mr - i
=> p[i] = min(p[j], mr - i)
2.若i在[mr, +无穷)
p[i] = 1, 同时扩张mr
mr: 右边界最靠右的回文串的右边界的值
mid : 最靠右的这个回文串的中心点
i:枚举字符串的下标
j: i关于mid对称的点
文字性解释:
1.在范围内:p[i] 关于最右回文串的对称字符串在(ml - mr) 范围内,那么j是对称字串的中心,p[i]=p[j]
2.不在范围内:因为(ml - mr)是最右回文串,所以p[i]等于其对称子串在(ml-mr)中的最大半径。因为其对称字串范围超过了(ml-mr),且无法扩展,即str[mr + 1] != str[ml].
所以此时p[i]就等于其对称字串在ml-mr范围内的半径,即mr - i;
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 2e7 + 10;
int n;
char a[N], b[N];
int p[N];
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;
}
void manacher()
{
int mr = 0, mid;
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;
}
}
}
int main()
{
cin >> a;
n = strlen(a);
init();
manacher();
int res = 0;
for(int i = 0; i < n; i++)
res = max(res, p[i]);
cout << res - 1;
return 0;
}
0 条评论
目前还没有评论...