abbcac
$#a#b#b#c#a#c#^
abbca
$#a#b#b#c#a#^
保证转化完都是奇数
原串里长度为x的回文串
对应新串里半径长度为x+1的回文串
则本题转化为求新串里长度最长回文串的半径 l后
答案 = l - 1
p[i]: 以S[i]为中心的最大回文串的半径长度
从前往后推
存最右回文串中心mid及右边界的下一个边界mr
1 i在[mid,mr]内部
|------|-----|-----|-----|-----
l j mid i mr
mid = (i+j)/2 => j = 2 * mid - i
1.1 j - p[j] >= l 以j为中心的最长回文串半径没有超过mid的半径的话
那么由i和j关于mid回文--> p[i] = p[j]
1.2 j - p[j] < l 以j为中心的最长回文串半径超过mid的半径的话
但此时以i为中心的回文不能超过mr,因为如果超过mr了,则如下图所示
以mid为中心的最长回文串的右边界就可以通过
np = rr - i
exp = rr - mr
[mr,rr] == [i-np,i-np+exp]
==[ll,j-np] == [j+np-exp,j+np]
|-----|------|-----|-----|-----|-----|
ll l j mid i mr rr
从而与p[mid]只能到mr矛盾
(⭐因为我们是先从mid开始扩展的,所以如果能扩到rr的话,在mid的时候就扩展到了)
所以为了保证右边界不超过mr
1.2.1 i在[mid,mr]内
p[i] >= min(p[j],mr-i)
(1) p[j]在p[mid]内
p[i] = p[j]
(2) p[j]在p[mid]左边界
p[i] 可能> p[j]
>的情况在j的左边界j-p[j]刚好到mid的左边界mid-p[mid]时,p[i]有可能通过向右延申有更大回文半径
(3) p[j]超过p[mid]左边界
p[i] = mr-i
1.2.2 i在(mr, )
因为说明此时所有回文串能到的最右mr都没到i,则i最长只有自己
p[i] = 1
什么时候更新mr:
i+p[i] > mr(前面所有求过的回文串最靠右的边界)
从p[i]继续往外扩展
while(s[i-p[i]] == s[i+p[i]])
p[i]++;
#include <iostream>
#include <cstring>
#include <algorithm>
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()
{
scanf("%s", a);
n = strlen(a);
init();
manacher();
int res = 0;
for (int i = 0; i < n; i ++ ) res = max(res, p[i]);
printf("%d\n", res - 1);
return 0;
}