【字符串】Manacher

Manacher算法的本质是计算以字符串中的“每个字符”和“每两个相邻字符之间的空隙”作为对称中心的最大回文串的长度。所以利用这个性质可以解决一系列与子串是否是回文串、子串有多少是回文串的问题。

namespace Manacher {
const int MAXN = 1.1e7;

int n;
char s[MAXN + 10];          // 1-index string
int len[2 * MAXN + 10];     // len[mid] means the longest extended length
// for every substr[l, r] that satisfies mid == l + r

void manacher (char *s) {
    n = strlen (s + 1);
    len[2] = 1;
    for (int i = 2, j = 0; i <= (n << 1); ++i) {
        int p = i >> 1, q = i - p;
        int r = ( (j + 1) >> 1) + len[j] - 1;
        len[i] = r < q ? 0 : min (r - q + 1, len[ (j << 1) - i]);
        while (p > len[i] - 1 && q + len[i] < n && s[p - len[i]] == s[q + len[i]])
            ++len[i];
        if (q + len[i] - 1 > r)
            j = i;
    }
}
}

using namespace Manacher;

心情复杂：过去这么多年都没有好好学习过这个算法，每次都是抄模板，终于碰壁了一次。

想理解上面的算法是怎么工作的，需要先理解朴素算法。这里的朴素算法是指用 \(O(n^2)\) 时间复杂度计算出字符串中每个对称中心的最长拓展长度。

朴素算法是分别处理长度为奇数和长度为偶数的字符串，如下：

const int MAXN = 1e6;

int n;
char s[MAXN + 10];          // 1-index string
int len[2 * MAXN + 10];     // len[lrs] means the longest extended length
// for every substr[l, r] that satisfies lrs == l + r

void bruteforce (char *s) {
    n = strlen (s + 1);
    for (int lrs = 2; lrs <= 2 * n; lrs += 2) {
        len[lrs] = 1;
        int lmid = lrs / 2, rmid = lrs - lmid;
        // lrs = 2, [1, 1]
        // lrs = 4, [2, 2] -> [1, 3]
        // lrs = 6, [3, 3] -> [2, 4] -> [1, 5]
        while (1 <= lmid - len[lrs] && rmid + len[lrs] <= n
                && s[lmid - len[lrs]] == s[rmid + len[lrs]]) {
            ++len[lrs];
        }
    }
    for (int lrs = 3; lrs <= 2 * n; lrs += 2) {
        len[lrs] = 0;
        int lmid = lrs / 2, rmid = lrs - lmid;
        // lrs = 3, [1, 2]
        // lrs = 5, [2, 3] -> [1, 4]
        // lrs = 7, [3, 4] -> [2, 5] -> [1, 6]
        while (1 <= lmid - len[lrs] && rmid + len[lrs] <= n
                && s[lmid - len[lrs]] == s[rmid + len[lrs]]) {
            ++len[lrs];
        }
    }
}

/**
Return the max length of palindrome substr[l, r] that satisfy l + r == lrs
*/
int max_length_palindrome (int lrs) {
    return 2 * len[lrs] - (lrs % 2 == 0);
}

bool is_palindrome (int l, int r) {
    int lrs = l + r;
    return max_length_palindrome (lrs) >= (r - l + 1);
}

然后观察发现其实他们大体上算法是可以合并化简的：

void bruteforce (char *s) {
    n = strlen (s + 1);
    for (int lrs = 2; lrs <= 2 * n; ++lrs) {
        len[lrs] = (lrs % 2 == 0);
        int lmid = lrs / 2, rmid = lrs - lmid;
        while (1 <= lmid - len[lrs] && rmid + len[lrs] <= n
                && s[lmid - len[lrs]] == s[rmid + len[lrs]]) {
            ++len[lrs];
        }
    }
}

其他可以替代的办法：字符串哈希、回文自动机、后缀数组

如果只是求最长回文串的长度和位置，而不包含“有多少个不同的回文子串”之类的信息的话，字符串哈希是可以用二分答案的长度然后枚举每个回文中心暴力判断的。