/*
预处理:
回文串长度个数为奇数,则其对称位置在某个字符。
否则在两个字符中间,非常不利于计算回文串长度。

处理方法:在字符串的两边加上#,任意两个字符之间加上#
字符串的长度 = 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 条评论

目前还没有评论...