luogu1210 回文检测

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
", l, r, L, R);
    printf("%d
", 1 + (r - l) / 2);
    for (int i = L; i <= R; i++)
        printf("%c", a[i]);
    return 0;
}

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