Manacher算法详解

一、简介

Manacher算法是用来解决“最长回文子串”的问题，它是一个时间复杂度为O(n)的算法，比起暴力方法O(n^3)和动态规划O(n^2)更为高效。本文将从算法思路、代码实现等多个方面详细介绍Manacher算法。

二、算法思路

Manacher算法的核心思想是利用已经得到的回文中心的信息来推断出更多的回文中心，从而得到最长回文子串的长度。每个回文中心都可以向两边扩展，扩展出来的字符串如果仍然是回文的，就可以得到新的回文中心。

可以分为以下两个步骤：

第一步：处理字符串

为了将奇数长度回文和偶数长度回文都统一处理，需要在每两个字符之间插入一个符号，例如“aa”插入符号后为“#a#a#”，”123″插入符号后为“#1#2#3#”。这样字符串的长度就变成了奇数。

第二步：计算最长回文长度

需要维护两个变量mx和id，其中mx表示当前在所有已经发现的回文串中，向右端点最远的那个回文串的右端点的位置，id表示该回文串的中心位置。最长回文长度即为mx减去id。

为什么要用mx和id？因为可以通过已经处理好的回文串来推断新的回文串，这样可以避免重复计算已经处理过的回文串。

如何推断新的回文串？在已知最右边的回文中心的情况下，依次向右遍历每个字符，并以该字符为中心向两边扩展，得到以该字符为中心的最长回文半径。

可能有人会问，最长回文子串的具体值是多少呢？本算法并没有直接计算回文子串的值，只是记录了最长回文子串的长度。如果需要得到具体的回文子串，可以通过最长回文子串的起点（mx-id）和长度（mx-id）计算得到。

三、代码实现

string manacher(string s) {
    string t = "$#";
    for (int i = 0; i < s.size(); i++) {
        t += s[i];
        t += "#";
    }
    vector<int> p(t.size(), 0);
    int id = 0, mx = 0; // id是最长回文串的中心，mx是最右边的，回文串能够触及到的最右边的位置
    int maxLen = 0, center = 0; // maxLen是最长回文长度，center是最长回文中心

    for (int i = 1; i  i) {
            p[i] = min(mx - i, p[2 * id - i]);
        } else {
            p[i] = 1;
        }
        while (t[i - p[i]] == t[i + p[i]]) {
            p[i]++;
        }
        if (mx < i + p[i]) {
            id = i;
            mx = i + p[i];
        }
        if (maxLen < p[i] - 1) { // 减去插入的#字符
            maxLen = p[i] - 1;
            center = i;
        }
    }

    return s.substr((center - maxLen) / 2, maxLen);
}

四、复杂度分析

Manacher算法的时间复杂度为O(n)，其中n为字符串长度。具体分析如下：

第一步处理字符串的时间复杂度为O(n)，因为需要插入2n+1个字符。

第二步计算最长回文长度的时间复杂度为O(n)，因为需要遍历2n+1个字符并计算每个字符的回文半径。

所以总时间复杂度为O(n)。

五、优化

Manacher算法有一些优化的细节，这里列举一下：

1、对字符串进行预处理

在字符串的开头增加一个特殊字符，这样就不需要在处理回文中心的时候特判边界情况了。同时，在每个字符之间插入一个符号（例如“#”），可以避免奇偶问题，使处理过程更为简单。

2、使用数组p在计算回文半径时，尽可能复用已经得到的回文信息

如果p[j]表示以j为中心的回文串的长度，而i的位置在[j-p[j], j+p[j]]之间，那么如果p[2 * j – i] >= p[j]，那么p[i]的初始值可以直接取p[2 * j – i]的值，这样就不用从头开始匹配了。

3、使用mx和id避免了重复计算的情况

mx表示当前在所有已经发现的回文串中，向右端点最远的那个回文串的右端点的位置，而id表示该回文串的中心位置。如果右边的回文串没有超过之前计算过的回文串右边界，就可以避免重复计算了。

六、总结

Manacher算法是一种高效的求解最长回文子串的方法，时间复杂度为O(n)。通过预处理字符串、复用已有回文信息以及使用mx和id等细节上的优化，可以进一步提高算法的效率。

原创文章，作者：FMJDR，如若转载，请注明出处：https://www.506064.com/n/343271.html