标准Manacher算法,TLE了
查看原帖
标准Manacher算法,TLE了
1127424
damuzhi楼主2024/5/30 15:15
#include <bits/stdc++.h>

using namespace std;

const int N = 22000002;
int n,P[N<<1];
char a[N],S[N<<1];

void change()
{
    n = strlen(a);
    int k = 0;
    S[k++] = '$',S[k++] = '#';//开头和第一个'#'
    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 + P[C] - i]);//合并两种情况
        else
            P[i] = 1;
        while(S[i+P[i]] == S[i-P[i]])//暴力中心扩展法
            P[i]++;
        if(i + P[i] > R)//替换
        {
            R = i + P[i];
            C = i;
        }

    }
}

int main()
{
    cin >> a;
    change();
    manacher();//计算每个中心点的最大回文串半径
    int ans = 1;
    for(int i = 0; i < n; i++)
        ans = max(ans,P[i]);
    cout << ans - 1 << '\n';
    return 0;
}
2024/5/30 15:15
加载中...