Manacher算法详解

Manacher 算法是求字符串最大回文子串最高效的算法，时间复杂度和空间复杂度都为O(n),相较于时间复杂度为O(n³)的暴力穷举和时间复杂度为O(n²)的动态规划算法具有明显的优势。算法的目的在于提高信息及资源的利用效率，减少不必要的计算。那么本文的主要内容主要分为两个部分，一是说明manacher算法的思想，二是给出相应java代码实现。抛砖引玉，如有错误请不吝赐教。

一 算法要点分析

---

求最大回文子串一般情况需要分奇数串和偶数串来进行分类讨论，而Manacher算法则通过一种处理方式将字符串都转化为奇数串来处理，即在首尾及每量个字符之间插入任意选定字符，比如在字符串 "asdsa" 中插 '#' 变为 "#a#s#d#s#a#" (其实插入任意字符都可以，因为插入后原字符仍与原字符进行比较，但是为了使初次接触此算法的同学便于理解，并且不去刻意做无用的“创新”，遂沿用‘#’，好像废话有点多)。

//字符串预处理
StringBuilder newStr = new StringBuilder();
newStr.append('#');
for (int i = 0; i < str.length(); i ++) {
     newStr.append(str.charAt(i));
     newStr.append('#');
    }

先求处理过的字符串每个位置上的最大回文字符串的回文半径r，这个半径 - 1 正好是原字符串以此位置为中心的最大回文字符串的长度。例如：

回文半径数组示图.png

所以问题将转化为求处理过的字符串每个位置上的最大回文字符串半径。

介绍算法前首先需要说明三个Manacher算法中会用到的三个概念。

• 从左向右遍历字符串已找到的回文子串最右边的字符位置right。
• 最右回文子串的中心位置id。
• 记录每个位置为中心时最大回文字符串的半径长度数组rad[]。

对称位置回文半径两种情况示图.png

如上图所示，id为最右回文子串的中心，right为最右回文子串的右边界，当计算某位置id+k时，可以利用其关于id对称的位置id-k的最大回文半径，从而避免重复计算，提高效率。此时分两种情况：
1 当rad[id-k] >= rad[id] - k 时，如图橙色区间超出蓝色区间，id+k 的最大回文半径最小是rad[id]-k，如图中与红色区间关于id对称的绿色区间。

2 当rad[id-k] < rad[id] - k 时，如图橙色区间未超出蓝色区间，id+k 的最大回文半径最小是rad[id-k]，如图中与红色区间关于id对称的绿色区间。
所以在任何情况下，rad[ id + k ] = min( rad [ id ] - k, rad[ id - k ] )。

二 完整函数代码

---

public static int getPalindromeLength(String str) {
        StringBuilder newStr = new StringBuilder();

        // 插入字符，统一奇偶性便于计算。
        newStr.append('#');
        for (int i = 0; i < str.length(); i++) {
            newStr.append(str.charAt(i));
            newStr.append('#');
        }

        // 用来记录每个位置的最大回文半径
        int[] rad = new int[newStr.length()];
        // 用来记录最右回文字符串的中心位置
        int id = -1;
        // 用来记录最右回文字符串的最右位置
        int right = -1;
        // 从左向右依次遍历
        for (int i = 0; i < newStr.length(); i++) {
            // 初始化每一位置最小半径至少为1
            int r = 1;
            // 从回文半径数获取计算过的回文半径，减少计算
            if (right >= i) {
                r = Math.min(rad[id] - i + id, rad[2 * id - i]);
                // 只有相等的情况才有可能找到最大的回文半径。
                if (rad[id] - i == rad[2 * id - i])
                    // 从上一步基础位置开会依次向两个方向比较，直到对称位置字符不同
                    while (i - r >= 0 && i + r < newStr.length()
                            && (newStr.charAt(i + r) == newStr.charAt(i - r))) {
                        r++;
                    }
            }

            // 当right相同是，取最左边的中心位置效率最高，所以不用更新。
            if (i + r - 1 > right) {
                right = i + r - 1;
                id = r;
            }
            // 更新回文半径数组
            rad[i] = r;

        }
        // 获取新字符串最大回文半径
        int maxLength = 1;
        for (int r : rad) {
            maxLength = r > maxLength ? r : maxLength;
        }
        // 原字符串最大回文长度为新字符串最大回文半径的长度 - 1
        return maxLength - 1;
    }

三 复杂度分析

---

* 空间复杂度 ：

新字符串长度与原字符串长度为线性关系，回文半径数组长度为新字符串长度，所以空间复杂度为O(n)。

* 时间复杂度 ：

时间复杂度分析示图.png

如上图所示，橙色区间为第id趟最大回文字符串，蓝色区间为第id+1趟最大回文字符串。

最坏情况下（全部字符相同)
从第三趟开始每次需要多比较两次（图中紫色区间），直到整个字符串的中心位置为止（ ≈ 2 / n 趟），之后每个位置比较次数为0。

最好情况下（原字符串每个字符皆不相）
每次只需比较1到2次，直到遍历完整个字符串（n趟）。

综上，此算法的平均时间复杂度为O(n)。

四 总结

---

manather算法首先对原字符串做预处理，以便于统一计算，并充分利用了已经经过计算得出的信息，减少了计算量，在最好情况和最差情况都具有线性的复杂度。