Manacher

正确读法：抹内A撤(马拉车)

(跟着假硕学英语)

我们把原来的字符串，通过玄学处理，变成只留下字母，且每两个字母之间有一个奇怪的字符的那种Manacher专用字符串。

建立双射关系f[i]表示a[i]在b中的位置（如果a[i]是字母），f_[i]表示b[i]在a中的位置（如果b[i]是字母）

然后对b数组跑Manacher

然后找最长回文子串回文中心的位置，通过这个位置直接在b数组中先找左右端点，然后在找到a数组中对应位置输出

数组要开到四万（下面的代码开了两万RE一个点，想抄题解的自己改一下）：

#include <bits/stdc++.h>

using namespace std;

char a[20010], b[20010];

int f[20010], f_[20010], res[20010];

int main()

{

    int p = 0;

    while((a[p] = getchar())!=EOF)p++;

    a[p]=0;

    int len = strlen(a), j = 1;

    memset(b, 0x25, sizeof(b));

    for (int i = 0; i < len; i++)

    {

        if(isalpha(a[i]))

        {

            f[i] = j;

            f_[j] = i;

            b[j] = a[i];

            if(islower(b[j]))

                b[j] -= 32;

            j+=2;

        }

    }

    //从[0,j)跑马拉车

    int more = 0, pos = 0;

    for (int i = 0; i < j; i++)

    {

        if (more > i)

            res[i] = min(res[2 * pos - i], more - i);

        else

            res[i] = 1;

        while (i + res[i] < j && i - res[i] >= 0 && b[i+res[i]] == b[i-res[i]])

            res[i]++;

        if (i + res[i] - 1 > more)

        {

            more = i + res[i] - 1;

            pos = i;

        }

    }

    int maxLengthPos = 0;

    for (int i = 1; i < j; i++)

        if(res[i] > res[maxLengthPos])

            maxLengthPos = i;

    int r = maxLengthPos + res[maxLengthPos] - 2, l = maxLengthPos - res[maxLengthPos] + 2;

    int L = f_[l], R = f_[r];

    //printf("%d %d %d %d\n", l, r, L, R);

    printf("%d\n", 1 + (r - l) / 2);

    for (int i = L; i <= R; i++)

        printf("%c", a[i]);

    return 0;

}

让我们一起膜拜大佬林瑞堂@olinr

manacher

luogu1210 回文检测

Manacher