题解 | 最长回文子串

// Manacher Algorithm
#include <bits/stdc++.h>
using namespace std;

const int N = 1e3; // 为了防止修改后的str数组越界,要开2倍多一点
char a[N],s[N]; // a为原字符数组,s为修改后的字符数组
int d[N]; // 回文字符串半径

// manacher算法用于获取回文半径
void manacher(char *s,int n)
{
    d[1] = 1; // 只有一个str，半径为1
    for(int i=2,l,r=1;i<=n;i++) // 从下标为2的字符开始,l,r初值随意
    {
        if(i<=r) // 若下标在加速盒子里面,简化计算
        {
            d[i] = min(d[l+r-i],r-i+1); // 获取最短的回文半径
        }
        while(s[i-d[i]] == s[i+d[i]]) // 若不在加速盒子内,则暴力中心扩展
        {
            d[i]++; 
        }
        if(i+d[i]-1 > r) // 若加速半径越出了加速盒子的右边界
        {
            l = i-d[i]+1; // 更新加速盒子的左边界
            r = i+d[i]-1;
        }
    }
}

int main()
{
    scanf("%s",a+1); // 从下标1开始输入
    int n = strlen(a+1),k=0; // k为修改后的str下标
    s[0] = '$',s[++k] = '#'; // s[0]为哨兵,s[1]为#
    for(int i=1;i<=n;i++) // 遍历输入原str和#
    {
        s[++k] = a[i];
        s[++k] = '#';
    }
    n = k; // 获取修改后的str长度
    manacher(s,n); // 马拉车算法获取回文半径
    int ans = 0; 
    for(int i=1;i<=n;i++)
    {
        ans = max(ans,d[i]); // 更新最大回文半径ans
    }
    printf("%d\n",ans-1); // 回文半径-1就是最大回文str的长度
    return 0;
}