MENU

Manacher算法

August 12, 2018 • Read: 131 • 算法

说明

给一个字符串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。这提供了一个很好思路,以后优化什么算法,从记录值来着手,说不定能发现一个更优秀的算法

例题

某歌面试题

Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment