88pts求助

P4287 [SHOI2011] 双倍回文

Watware @ 2021-12-31 17:33:44

manacher算法只有88pts,最后一个点WA掉,不知道为什么

#include <bits/stdc++.h>
using namespace std;

const int M = 15010000;

char str[M];
int l, sz, p[M], ans = 0, mid;

int main()
{
    scanf("%d", &l);
    char c = getchar();
    while (!isalpha(c))
        c = getchar();
    str[1] = '[';
    for (int i = 1; i <= l; i++)
    {
        str[i << 1] = c;
        str[i << 1 | 1] = '|';
        c = getchar();
    }
    str[l + 1 << 1] = ']';
    sz = l << 1 | 1;
    for (int c = 0, mx = 0, i = 1; i <= sz; i++)
    {
        p[i] = 1;
        if (i <= mx)
            p[i] = min(p[2 * c - i], mx - i);
        if (str[i] != '|')
            while (str[i - p[i]] == str[i + p[i]])
                p[i]++;
        else
            while (str[i - p[i]] == str[i + p[i]])
            {
                if ((p[i] & 2) && p[i] >= 3)
                {
                    mid = 2 * i - p[i] - 1 >> 1;
                    if (p[mid] >= i - mid)
                        ans = max(ans, p[i] + 1);
                }
                p[i]++;
            }
        if (i + p[i] > mx)
            mx = i + p[i], c = i;
    }
    printf("%d", ans);
    return 0;
}

|