Manacher算法

2024-08-10

采用动态规划方法,用于求解一个字符串中的最长回文子串

#include <bits/stdc++.h>
#define io cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
#define LL long long
#define ULL unsigned long long
#define EPS 1e-8
#define INF 0x7fffffff
#define SUB -INF - 1
using namespace std;
const int N = 1000002;
int n, P[N << 1];
char a[N], S[N << 1];
void change()
{
    S[0] = '$', S[1] = '#';
    int k = 2;
    for (int i = 0; i < n; i++)
    {
        S[k++] = a[i];
        S[k++] = '#';
    }
    S[k++] = '&';
    n = k;
}
void manacher()
{
    int R = 0, C;
    for (int i = 1; i < n; i++)
    {
        if (i < R)
            P[i] = min(P[(C << 1) - i], P[C] + C - i);
        else
            P[i] = 1;
        while (S[i + P[i]] == S[i - P[i]])
            P[i]++;
        if (P[i] + i > R)
        {
            R = P[i] + i;
            C = i;
        }
    }
}
int main()
{
    io;
    scanf("%s", a);
    n = strlen(a);
    change();
    manacher();
    int ans = 1;
    for (int i = 0; i < n; i++)
        ans = max(ans, P[i]);
    printf("%d", ans - 1);
    return 0;
}