算法学习之Manacher算法

问题引入

抛出问题：指定一个字符串 s，如何求解 s 中 最长回文子串 的长度？

示例如图

---

常规解法

中心拓展法图示及思路

遍历字符串中的每一个元素，分别以当前元素为中心，向左右两边进行拓展，直到左右两边的元素不一致时，记录当前元素能取得的回文子串长度。经过一轮的遍历最终可以获得最大的回文子串长度。

是否存在当前思路未考虑到的情况

当字符串为 babbab 时，按照上面的思路进行求解，能取得的最大回文子串长度为3，但是实际上应该为6。

可以发现当字符串为偶数时，会有部分情况根据上述的思路无法求解到正确的最大回文子串长度。

为什么会出现这样的情况呢？

我的想法是在求回文子串时，中心拓展法需要一个中心轴，而思路中以元素作为中心轴，当遇到像babbab这样的字符串时，想要求出正确的回文子串长度应当在字符串的正中心位置作为中心轴，但目前思路无法做到。

改进：添加辅助字符（除了这种改进方法还有其他方法）

使用任意字符向原来的字符串的间隙中插入，如：babad => #b#a#b#a#d#

可以看到使用辅助字符充当中心轴，即可实现取得正确回文子串长度。

tip: 这里的辅助字符可以是任意字符，即使是a、b..等等字符也不会影响到原字符串。

中心拓展法的实现代码

// 求字符串s的最大回文子串长度
public static int longestPalindrome(String s) {
    char[] ncs = newString(s);
    // 初始化最大值为自身长度1
    int ans = 1;
    // 遍历每一个元素
    for (int i = 0; i < ncs.length; i++) {
        // 向左右两边拓展
        int l = i, r = i;
        while (l >= 0 && r < ncs.length && ncs[l] == ncs[r]) {
            l--;
            r++;
        }
        // 更新最大回文子串
        ans = Math.max(ans, (r - l) / 2 - 1);
    }
    return ans;
}

// 插入辅助字符构造新字符串
public static char[] newString(String str) {
    char[] cs = str.toCharArray();
    char[] res = new char[str.length() * 2 + 1];
    int index = 0;
    for (int i = 0; i < res.length; i++) {
        // 偶数位置插入辅助字符，奇数位置插入原字符串字符
        // babad => #b#a#b#a#d#
        res[i] = (i & 1) == 0 ? '#' : cs[index++];
    }
    return res;
}

从代码中可以分析出当前解法的时间复杂度为 O(N2)O(N²)O(N2)

接下来介绍 Manacher算法 将时间复杂度优化成 O(N)O(N)O(N)

---

Manacher 算法思路

Manacher算法之所以只需要使用 O(N)O(N)O(N) 的时间复杂度的原因在于 在遍历每个字符进行中心拓展寻找回文子串时，分情况使得一些字符可以快速得出回文长度，不再需要进行中心拓展，从而使得 O(N2)O(N²)O(N2) 优化为 O(N)O(N)O(N)。

接下来将按情况介绍如何快速取得一些字符的回文子串长度（字符的回文子串长度指的是以该字符为中心轴进行中心拓展取得的最大回文子串长度）。

在分情况前，先引入四个前置概念

1. 回文半径：以当前字符为中心轴，能取得的最长回文子串就是回文直径，回文半径即为从中心点到右边（左边）的长度。
2. 回文半径数组：字符串中以每个字符为中心轴，都会有对应自己的回文半径，回文半径数组指使用一个数组记录字符串中每个字符的对应回文半径。
3. 最右边界R：在遍历字符串的每个字符时，遍历过的字符都会有自己对应的回文半径及回文字串能到达的最右端距离，而最右边界指的是在当前遍历过的字符里取得回文字串所能到达最右端的最远距离（这个不好理解看图示）
4. 中心点C：中心点与最右边界起到联系，在当前遍历到字符里取得的最右边界对应的那个字符的下标即为中心点，所以每当在遍历字符时，随着最右边界的更新，中心点也会随之更新（初始化时 最右边界R = -1；中心点C = -1）。

• 上图中所遍历过的字符中能取得的 最右边界R(右端最远距离) 为 8，对应的 中心点C 为5；
• 可以看到中心点的更新是随着最右边界的更新而更新，每次更新中心点取得当前位置的字符串下标；
• 可以看到下标位置7所能到达的最远右端距离也为8，但是并不更新，因为只有超过原先的最右边界R才进行更新；

补充一下 每个字符取到的最远右端距离 的计算:

当前下标为i的字符取到的最远右端距离=i+回文半径数组[i]−1当前下标为i的字符取到的最远右端距离 = i + 回文半径数组[i] - 1当前下标为i的字符取到的最远右端距离=i+回文半径数组[i]−1

如上图的例子：

• 下标为5的字符b能到达的最右端距离为 5 + 4 - 1 = 8;
• 下标为6的字符#能到达的最右端距离为 6 + 1 - 1 = 6;
• 下标为7的字符a能到达的最右距离为 7 + 2 - 1 = 8;

---

理清上面的四个概念之后，想要获取字符串中最长回文子串的长度，即遍历字符串的字符，更新每个字符对应的回文半径（即更新回文半径数组），最后取得数组中最大的值即为最长回文子串的回文半径，通过回文半径即可获得最长回文子串的长度。

Manacher算法优化在于更新回文半径数组时对于某些情况下的字符可以快速获得回文半径，接下来将按照不同情况分类讨论。

情况一：当前遍历的字符下标不在 最右边界R 内部，此时只能暴力更新（中心拓展法）

如上图，当前遍历到字符b（下标位置1）处时，如何更新该位置的回文半径？

此时的最右边界R为0，而需要求解回文半径的字符b的下标位置为1，即当前字符下标位置不在最右边界R的内部。

这种情况无法快速获得回文半径，只能使用中心拓展法暴力更新。

---

情况二：当前遍历的字符下标 i 在 最右边界R 内部，且 i 以中心点为对称轴得到的对称点 i'的 回文子串 完全落在 中心点的回文字串 内部，此时 i的回文半径可以直接取 i'的回文半径

根据上图可以更清晰的了解情况二的意思。

强调一个非常重要的边界问题：这里的i'的回文子串需要完全落在中心点的回文子串内部，这里的内部不包括中心点的回文子串的边界（即上图中的下标2和12不算内部）。

接下来说明为什么在这种情况下通过对称点可以快速拿到回文半径。

通过上图的证明可以明确的知道i'的回文半径与i的回文半径一致，所以可以直接快速获得，这样就省去了暴力更新的时间，起到优化。

---

情况三：当前遍历的字符下标 i 在 最右边界R 内部，且 i 以中心点为对称轴得到的对称点 i'的 回文子串 超出了 中心点的回文字串 的范围，此时 i的回文半径可以直接取为 最右边界R−i+1最右边界R - i + 1最右边界R−i+1

根据上图可以更清晰的了解情况三的意思。

接下来说明为什么在这种情况下可以通过 最右边界R−i+1最右边界R - i + 1最右边界R−i+1 快速取得i的回文半径。

通过上图证明可以直接通过 最右边界R−i+1最右边界R - i + 1最右边界R−i+1 快速获得i的回文半径，省去暴力更新的时间，起到优化。

---

情况四：当前遍历的字符下标 i 在 最右边界R 内部，且 i 以中心点为对称轴得到的对称点 i'的 回文子串 压线 中心点的回文字串 的边界，此时 i的回文半径无法直接获取，只能获取其中的一部分，剩余的部分需要向外拓展更新

根据上图可以更清晰的了解情况四的意思。

接下来说明为什么在这种情况无法获取完整的回文半径。

由于缺少条件所以无法确定i的回文半径，所以这种情况下无法快速获得i的回文半径，仍然需要拓展更新。

---

最后小结一下

Manacher算法基本思想与KMP类似，通过更新一个数组存储每个字符的回文半径长度从而取得最长的回文子串长度。

上面按照情况分类讨论可知：情况二和情况三是可以直接获取字符的回文半径，情况一和情况四则需要采用中心拓展的方式向左右两边更新获取最终的回文半径。

---

Manacher 算法代码实现

先上代码

// 求字符串s的最大回文子串长度
public static int longestPalindrome(String s) {
    // 判断边界
    if (s == null || s.length() == 0) return 0;
    // 插入辅助字符构建新字符串
    char[] ncs = newString(s);
    // 最长回文半径，初始化单个字符的回文半径为1
    int max = 1;
    // 构造回文半径数组
    int[] pr = new int[ncs.length];
    // 初始化最右边界与中心点
    int R = -1, C = -1;

    // 遍历字符串的字符
    for (int i = 0; i < ncs.length; i++) {

        // 统一处理
        pr[i] = R > i ? Math.min(pr[2 * C - i], R - i + 1) : 1;

        // 情况一与情况四进行中心拓展
        // 其余不用的会直接退出循环（因为 ncs[i + pr[i]] == ncs[i - pr[i]] 对比两边时，情况二、三已经是能到达的最长回文子串了，所以到这一步会自动退出循环）
        while (i + pr[i] < ncs.length && i - pr[i] >= 0 && ncs[i + pr[i]] == ncs[i - pr[i]]) {
            pr[i]++;
        }
        // 当前字符的最远右端距离
        int curPr = i + pr[i] - 1;
        // 判断是否需要更新R和C
        if (curPr > R) {
            R = curPr;
            C = i;
        }
        // 更新最长回文半径
        max = Math.max(max, pr[i]);
    }

    // 返回最长回文子串长度（为什么直接回文半径-1因为要去掉辅助字符）
    return max - 1;
}

// 插入辅助字符构造新字符串
public static char[] newString(String str) {
    char[] cs = str.toCharArray();
    char[] res = new char[str.length() * 2 + 1];
    int index = 0;
    for (int i = 0; i < res.length; i++) {
        // 偶数位置插入辅助字符，技术位置插入原字符串字符
        // babad => #b#a#b#a#d#
        res[i] = (i & 1) == 0 ? '#' : cs[index++];
    }
    return res;
}

一处细节讲解

// 统一处理
pr[i] = R > i ? Math.min(pr[2 * C - i], R - i + 1) : 1;

为什么这里做统一处理？

这样子可以减少代码冗余，统一处理指先拿到当前字符的可以快速拿到的回文半径长度，之后有需要向外拓展的就执行向外拓展，不需要的直接跳过。

怎么做到一行代码就能把上面四种情况概括完的？

• pr[2 * C - i] 指的是 对称点 i'的回文半径， R - i + 1 指的是 i 到 最右边界R 的长度。
• 情况一，i 不在 R 内，即 R > i，此时直接返回1，因为这种情况能快速拿到的回文半径就是自身长度1了。
• i 在 R 内，即 R <= i 时:
  • 情况二，i 的对称点 i'在 中心点回文子串内部，此时可以直接快速获取最长回文半径，应该返回 'i''的回文半径（即pr[2 * C - i]）, 这种情况下 pr[2 * C - i] 一定小于 R - i + 1的，有疑问的可以回去上面的案例看。
  • 情况三，i 的对称点 i'超出了中心点回文子串的范围，此时可以直接快速获取最长回文半径，应该返回 R - i + 1, 并且这种情况下 R - i + 1 一定小于 pr[2 * C - i]的，同样有疑问的可以回去上面案例看看。
  • 情况四，i 的对称点 i' 压线 中心点回文子串的边界，此时其实 R - i + 1 和 pr[2 * C - i]是相等的，所以返回哪个都行，并且这种情况只是拿到当前最短回文半径长度，后续还是需要向外拓展更新最长回文半径长度的。

---

最后附上一个力扣的相似题目：5. 最长回文子串 - 力扣（Leetcode）

感觉这篇文章有帮助的可以去试试上面这道题练练手