manacher WA 37pts 求条
查看原帖
manacher WA 37pts 求条
664034
_xxxxx_楼主2024/8/6 20:06

rt,一直调不出来,快红温了

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
char s[N], a[N];
int len;
void init()
{
    int now = strlen(s);
    a[0] = '@';
    len = 1;
    for(int i = 0; i < now; i++)
    {
        a[len++] = '#';
        a[len++] = s[i];
    }
    a[len++] = '#';
    a[len] = '!';
}
int p[N];
int lm[N], rm[N];
void manacher()
{
    int mr = 0, mid;
    for(int i = 1; i <= len; i++)
    {
        if(mr > i) p[i] = min(p[(mid << 1) - i], mr - i);
        else p[i] = 1;
        while(a[i + p[i]] == a[i - p[i]]) p[i]++;
        if(i + p[i] > mr) mr = i + p[i], mid = i;
        lm[i + p[i] - 1] = max(p[i + p[i] - 1], p[i] - 1);
        rm[i - p[i] + 1] = max(p[i - p[i] + 1], p[i] - 1);
    }
}
signed main()
{
    scanf("%s", s);
    init();
    manacher();
    for(int i = len; i >= 3; i -= 2) lm[i] = max(lm[i], lm[i + 2] - 2);
    for(int i = 3; i <= len; i += 2) rm[i] = max(rm[i], rm[i - 2] - 2);
    int mx = 0;
    for(int i = 3; i <= len; i += 2) if(lm[i] && rm[i]) mx = max(mx, lm[i] + rm[i]);
    cout << mx << endl;
    return 0;
}
2024/8/6 20:06
加载中...