Manacher算法

Manacher又叫"马拉车"算法，它可以在O(N)的平均时间复杂度下面找到一个字符串的最长回文子串。

题目

LeetCode5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

算法思路

manacher

预处理字符串

预处理的主要目的是保证字符串长度永远是奇数，总可以划分成等量的左右两部分，这样一定有一个确切的位置是最大回文中心位置。那么实现方式就是将原始字符串加上虚轴。如abba加上虚轴之后变为#a#b#b#a#

Manacher思想

• 定义一个radius数组，长度为加上虚轴之后的字符串的长度。数组中的每一个位置表示当前位置的字符最大回文半径。如#a#b#b#a#的最大回文半径数组为[1,2,1,2,5,2,1,2,1]
• 定义一个最大回文右边界R,它表示当前字符和前面的所有字符，加上他门各自的回文半径，所能走到最右边的位置。
• 定义一个表示当前最大回文右边界中心的指针C。
• 定义一对可以确定最大回文子串的maxCenter和maxR
• 然后就是分情况讨论：
  • case1：如果当前位置在最大回文右边界里面，首先检查当前的i位置以当前的最大回文中C的对称点j的回文半径，然后计算当前的R - i与j的回文半径取较小的即可。
    -case2: 如果当前位置在最大回文右边界上面或者右边，则默认半径为1，进行中心扩展，更新最大回文右边界R和回文中心C。

实列

• 理清思路，直接代码实现：

    public String testManacher(String s) {
        // 首先将字符串加上虚轴
        char[] chars = new char[s.length() * 2 + 1];
        int n = chars.length;
        for (int i = 0; i < n; i++) {
            chars[i] = i % 2 == 0 ? '#' : s.charAt(i/2);
        }
        // 创建记录最大回文半径的数组, 最大回文右边界和回文中心
        int[] radius = new int[n];
        int R = -1;
        int C = -1;
        for (int i = 0; i < n; i++) {
            radius[i] = R > i ? Math.min(R - i, radius[2*C-i]) : 1;
            // 进行中心扩展
            while(i + radius[i] < n && i - radius[i] >= 0) {
                if(chars[i - radius[i]] == chars[i + radius[i]]){
                    radius[i]++;
                }else{
                    break;
                }
            }
            // 更新最大回文半径
            if(i + radius[i] > R){
                R = i + radius[i];
                C = i;
            }
        }
        // 然后就是找出最长的回文字符
        int maxLen = radius[0];
        int maxC = 0;
        for (int i = 1; i < n; i++) {
            if(radius[i] > maxLen){
                maxLen = radius[i];
                maxC = i;
            }
        }
        // 计算出回文串的左右边界
        int start = (maxC - maxLen + 1) / 2;   // 尝试出来的
        int end = start + (maxLen - 1);
        return s.substring(start,end);
    }

补充

• 求出结果之后，记maxLen为最大的回文半径，maxC为回文中心
• 则最大回文子串的起始位置在(maxC - maxLen + 1) / 2, 终止位置为start + maxLen - 1。

---

衍生题目

给定一个字符串，向字符串后面添加最短的字符串，使其成为回文字符串

思路

• 根据马拉车算法的思想，一直计算最大右边界的停靠位置
• 一旦右边界到达了最后一个元素的位置时，停止
• 向左找到左边界
• 然后将左边界左边的所有字符逆序加到子序串后面

代码

    public static String shortestEnd2(String s) {
        // 首先将字符串加上虚轴
        char[] chars = new char[s.length() * 2 + 1];
        int n = chars.length;
        for (int i = 0; i < n; i++) {
            chars[i] = i % 2 == 0 ? '#' : s.charAt(i/2);
        }
        // 创建记录最大回文半径的数组, 最大回文右边界和回文中心
        int[] radius = new int[n];
        int R = -1;
        int C = -1;
        int maxLeft = -1;   // 记录最大回文左边界
        for (int i = 0; i < n; i++) {
            radius[i] = R > i ? Math.min(R - i, radius[2*C-i]) : 1;
            // 进行中心扩展
            while(i + radius[i] < n && i - radius[i] >= 0) {
                if(chars[i - radius[i]] == chars[i + radius[i]]){
                    radius[i]++;
                }else{
                    break;
                }
            }
            // 更新最大回文半径
            if(i + radius[i] > R){
                R = i + radius[i];
                C = i;
            }
            if(R == n){
                maxLeft = radius[i];
                break;
            }
        }
        StringBuilder res = new StringBuilder();
        for (int i = maxLeft; i >= 0; i--) {
            if(chars[i] != '#'){
                res.append(chars[i]);
            }
        }
        return res.toString();
    }