Manacher 算法

说明展开目录

给一个字符串 str，要求用 O (n) 的时间复杂度求出其中最长回文子串的长度

实现步骤展开目录

基本过程展开目录

求最大回文子串的长度一般要看原串的长度是奇数还是偶数，然后分别求得，但 Manacher 算法的第一个神奇之处就是把两种字符串都化为长度为奇数，从而简化计算：

public static char[] manacherString(String str) {
    char[] charArr = str.toCharArray();
    char[] res = new char[str.length() * 2 + 1];
    int index = 0;
    for(int i = 0;i <= res.length;i++) 
        res[i] = (i & 1) == 0 ? '#' : charArr[index++];
    return res;
}

例如原来是 aaaba，变化之后就是 #a#a#a#b#a#，无论原来是奇数还是偶数，变化之后都是奇数，方便处理

概念引入展开目录

manacher 算法引入三个重要概念：

1. 已知回文串的中心位置 C
2. 回文串的最右边界 R
3. 每个字符的回文半径数组 pArr

C 就是不断遍历的位置，只会向右不会向左。R 就是最远的回文半径到了右边哪，有更大的就更新，没有就不变，所以 R 只会越来越向右，不会回退。pArr [] 就是把每个位置的回文半径保存起来

确定回文半径展开目录

假设现在求出了 pArr [0,...,i-1]，现在要求 i 的值，分三种情况

如图，黑色部分是当前求出的最长回文直径，C 是这个最长回文直径的回文中心，现在要求的是 i 位置的最长回文半径是多少。蓝色部分是 i 关于 c 的对称点 i' 的回文半径，具体值就是 pArr [i']，现在的情况是蓝色的左边界超过了 C 的左边界，那么 i 的回文半径就确定是 pArr [i]=R - i，为什么不可能更长，假设 i 的回文半径跟 i' 是一样的，那 i 的回文半径就一定能伸展到 R 的外面，那么这样的话黑色部分应该也会伸长，可是黑色部分只有这么长，说明 R 后面的字符不足以给 i 构成更长的回文半径
如图，蓝色部分在黑色部分里面，这是第二种情况，那就很简单了，pArr [i] = pArr [i']
最后一种情况，如图，蓝色部分正好和黑色部分的边界重合，这个时候就不能肯定 R 后面的字符能否是的 i' 的回文半径更长，需要去判断
其实还有一种情况，就是 i 如果在 R 的外面，这种情况就只能暴力去扩展，看 i 的最长回文半径有多长。

manacher 代码展开目录

public static char[] manacherString(String str) {
    char[] charArr = str.toCharArray();
    char[] res = new char[str.length() * 2 + 1];
    int index = 0;
    for(int i = 0;i < res.length;i++)
        res[i] = (i & 1) == 0 ? '#' : charArr[index++];
    return res;
}
public static int maxLcpsLength(String str) {
    if(str == null || str.length() == 0) 
        return 0;
    char[] charArr = manacherString(str);
    int[] pArr = new int[charArr.length];//回文半径数组
    int C = -1,R = -1;//回文中心和回文最右边界
    int max = Integer.MIN_VALUE;
    for(int i = 0;i != charArr.length;i++) {
        pArr[i] = R > i ? Math.min(pArr[2 * C - i],R - i) : 1;
        while(i + pArr[i] < charArr.length && i - pArr[i] > -1) {
            if(charArr[i + pArr[i]] == charArr[i - pArr[i]])
                pArr[i]++;
            else 
                break;
        }
        if(i + pArr[i] > R) {
            R = i + pArr[i];
            C = i;
        }
        max = Math.max(max,pArr[i]);
    }
    return max - 1;
}

总结展开目录

看到 manacher 的算法流程，我想到了另一个算法 ——kmp，两者最初的方法时间复杂度都是 O ($n^2$)，但是由于通过各种方法，使得有一个参照的东西能够加快进度，时间复杂度变为 O (n)，比方说 kmp 里，加速的东西就是 next 数组，而 manacher 就是回文半径数组 pArr。这提供了一个很好思路，以后优化什么算法，从记录值来着手，说不定能发现一个更优秀的算法

例题展开目录

某歌面试题