Manacher 学习笔记

Manacher 可在 的时间内求出一个字符串以每个位置为中心的最长回文子串。

为了避免分类讨论,在字符串的首部的尾部添加两个不同的在串中没有出现过的字符(这里分别使用 @ 和空白字符 \0),每两个字符之间加入另一个在串中没有出现过的字符(这里使用 $)。这样,原串中长度为奇数和偶数的回文串的长度均变为奇数,且原串中回文串的长度为新串回文串半径减一。

设置两个状态 表示当前已找到的回文串中,向右延伸最远的中心位置, 表示其右端点。

表示(新串中)第 个位置的回文半径(回文串长度的一半,包括第 个字符)按从左到右的顺序求解,枚举到第 个字符时,分三种情况考虑:

关于 的对称点,即

,即向右延伸最远的回文子串(黑色)没有覆盖 ,此时只有

,即向右延伸最远的回文子串(黑色)覆盖了 ,并且以 为中心的最长回文子串完全与以 为中心的最长回文子串对称(蓝色),此时一定有 ,即

,即向右延伸最远的回文子串(黑色)覆盖了 ,但没有覆盖以 为中心的最长回文子串的对称位置串,所以 只能取被覆盖的(黄色)一部分,即

代码(POJ 3974

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

const int MAXN = 1000000;

// s1 原串,s2 新串
char s1[MAXN + 2], s2[MAXN * 2 + 3];
int n, len, r[MAXN * 2 + 3];

inline void prepare()
{
    n = strlen(s1);

    s2[++len] = '@'; // 边界字符
    s2[++len] = '
;
    for (int i = 0; i < n; i++)
    {
        s2[++len] = s1[i];
        s2[++len] = '
;
    }

    s2[len + 1] = '\0'; // 使用 0 作为结束字符和边界字符
}

inline void manacher()
{
    // 新字符串首部为 '@',尾部为 '\0'(空字符),中间为 '

    int right = 0, mid = 0; // right 当前回文最右点,mid 是 right 对应的回文中心
    for (int i = 1; i <= len; i++)
    {
        int x;
        if (right < i) x = 1;
        else x = std::min(r[mid * 2 - i], right - i);

        // 逐位匹配
        while (s2[i + x] == s2[i - x]) ++x;

        // 更新最右点
        if (i + x > right)
        {
            right = i + x;
            mid = i;
        }

        r[i] = x;
    }
}

int main() {
    int T = 0;
    while (scanf("%s", s1), memcmp(s1, "END", 4) != 0)
    {
        prepare();
        manacher();

        // printf("%s\n", s2 + 1);
        // for (int i = 1; i <= len; i++) printf("%d%c", r[i], i == len ? '\n' : ' ');

        int ans = 0;
        for (int i = 1; i <= len; i++) ans = std::max(ans, r[i] - 1);
        printf("Case %d: %d\n", ++T, ans);

        len = 0;
    }

    return 0;
}