P3805求助,红题做不出来!#9,#15TLE
  • 板块学术版
  • 楼主damuzhi
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/5/30 15:29
  • 上次更新2024/5/30 15:50:16
查看原帖
P3805求助,红题做不出来!#9,#15TLE
1127424
damuzhi楼主2024/5/30 15:29
#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:29
加载中...