PTA A_1040 Longest Symmetric String

798236606

传送门：https://pintia.cn/problem-sets/9 ... /994805446102073344

解：
manacher算法

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 1e3 + 10;

char a[maxn];
char b[maxn * 2];
int p[maxn * 2];

int init(char *a)
{

    b[0] = '!';
    b[1] = '#';

    int j = 2;

    for (int i = 0; i < strlen(a); ++i)
    {
        b[j++] = a[i];
        b[j++] = '#';
    }
    b[j] = '\0';

    return j;
}

int manacher(char *a)
{
    int len = init(a);
    int id = -1, mx = 0, ans = -1;

    for (int i = 1; i < len; ++i)
    {
        p[i] = (i < mx) ? min(p[2 * id - i], mx - i) : 1;
    
        while (b[i - p[i]] == b[i + p[i]]) ++p[i];

        if (i + p[i] > mx)
        {
            mx = i + p[i];
            id = i;
        }

        if (p[i] > ans) ans = p[i];
    }

    return ans - 1;
}

int main(void)
{
    // freopen("input.txt", "r", stdin);
    scanf("%[^\n]", a);

    printf("%d", manacher(a));

    return 0;
}