推荐分享 Manacher 算法详解

Manacher算法经典应用：计算最大回文字串，时间复杂度：O(n)

#include <iostream>
#include <cstring>

using namespace std;

const int N = 2e6 + 10;

char str[N];
int p[N], len;

int manacher(string s)
{
    // 初始化新串
    str[len] = '!';
    str[++ len] = '#';
    for (int i = 0; i < s.size(); i ++)
    {
        str[++ len] = s[i];
        str[++ len] = '#';
    }
    str[len + 1] = '@';

    int rt = 0, mid = 0, res = 0;
    for (int i = 1; i <= len; i ++)
    {
        if (i >= rt) p[i] = 1;
        else p[i] = min(p[2 * mid - i], rt - i);
        while (str[i + p[i]] == str[i - p[i]]) p[i] ++;
        if (i + p[i] > rt) 
        {
            rt = i + p[i];
            mid = i;
        }
        res = max(res, p[i] - 1);
    }
    return res;
}

int main()
{
    string s;
    getline(cin, s);

    int res = manacher(s);

    cout << res;

    return 0;
}