马拉车算法是计算字符串中最长回文串的算法,时间复杂度为O(n);

预处理

一般而言,回文串分为奇回文和偶回文,马拉车对字符串做了特殊处理,使得只有奇回文。

原文:abba(偶) 处理后:#a#b#b#a(len=9)
原文:aba(奇) 处理后:#a#b#a#(len=7)

计算最长回文子串长度

cabbaf为例,预处理后的子串变为#c#a#b#b#a#f#,变成一个字符数组arr[]。定义辅助数组int[]p,p的长度和arr长度一致,p[i]表示,以a[i]为字符中心的回文串半径。p[i]=1表示只有arr[i]本身是回文串。

i      0 1 2 3 4 5 6 7 8 9 A B C
arr[i] # c # a # b # b # a # f #  
p[i]   1 2 1 2 1 2 5 2 1 2 1 1 1

分析pi与回文串长度的关系

①aba:#a#b#a#-->3:4
②abba:#a#b#b#a#-->4:5
因此,int maxLength=p[i]-1
证明也比较简单:以arr[i]为中心的回文串,其长度就为2*p[i]-1,可以观察到回文子串中,所有的分隔符比其他字符多1,即分隔符为p[i],所以
maxLength=2*p[i]-1-p[i]=p[i]-1

计算最长回文子串的起始索引

知道了最长的回文子串的长度,还需要知道它的索引值。
①以cabbaf(偶回文)为例,p[6]=5是最长半径,用6(i)-5得到1恰好是abba的起始索引。
②以aba(奇回文),可以求得p[3]=4是最长半径,3-4下标越界。
因此在偶回文的情况下,满足下标-半径==起始索引。
因为奇数不满足,那就在奇数前面加特殊符号$,前面加了不满足奇数,因此后面还得加一个@
继续看偶回文:

i       0 1 2 3 4 5 6 7 8 9 A B C D 
arr[i]  $ # c # a # b # b # a # f # 
p[i]      1 2 1 2 1 2 3 2 1 2 1 2 1

易得p[7]=5,7-5=2,2/2=1,而奇回文aba i-半径为0,除2还是0;

结论:int index=(i-p[i])/2

计算p数组

i       0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
arr[i]  $ # c # a # b # b # a  #  f  #  @ 
p[i]      1 2 1 2 1 2 5 2 1 2  1  2  1

p数组是从左往右算的,当计算p[i]时,p[j](0<=j<i)已经计算完毕。
不妨设P为之前计算中最长回文子串的右端点的最大值,并且设取到这个最大值的中心位置为p0,分两种情况:

i<=P

图中T为arr数组
找i相对于p0对称位置,设为j,
①如果p[j]<p-i,如上图,
那么说明以j为中的回文子串一定在以p0为中心的回文子串内部,并且i和j关于po对称,易得p[i]=p[j]


②如果p[j]>=p-i,
说明以i为中心回文串延伸到P之外,大于P的位置,还没有匹配,需要逐一匹配,更新P、p0、p[i];

i>p

说明以i为中心的回文串还没有匹配,只能老老实一个个匹配。

代码

public static String Manacher(String s) {
    if (s.length() < 2) {
        return s;
    }
    // 第一步:预处理
    String t = "$";
    for (int i=0; i<s.length(); i++) {
        t += "#" + s.charAt(i);
    }
    // 尾部再加上字符@,变为奇数长度字符串
    t += "#@";


    // 第二步:计算数组p
    int n = t.length();
    int[] p = new int[n];
    int id = 0, mx = 0;//id即为图中的p0,mx即为图中的P
    int maxLength = -1;
    // 最长回文子串的中心位置索引
    int index = 0;
    for (int j=1; j<n-1; j++) {

        p[j] = mx > j ? Math.min(p[2*id-j], mx-j) : 1;
        // 向左右两边延伸,扩展右边界
        while (t.charAt(j+p[j]) == t.charAt(j-p[j])) {
            p[j]++;
        }
        // 如果回文子串的右边界超过了mx,则需要更新mx和id的值
        if (mx < p[j] + j) {
            mx = p[j] + j;
            id = j;
        }
        // 如果回文子串的长度大于maxLength,则更新maxLength和index的值
        if (maxLength < p[j] - 1) {
            maxLength = p[j] - 1;
            index = j;
        }
    }
    // 第三步:截取字符串,输出结果
    int start = (index-maxLength)/2;
    return s.substring(start, start + maxLength);
}

代码解析

1、第一部分为构造arr数组,头部添加$,尾部添加@
2、第二部分为计算p数组,是主要部分,依上述需分2类:

①i<mx:此时,p[i]最小为min(p[j],mx-j),首先p[i]=p[j]是显然的,注意需要加一个条件p[i]的半径不能超过i到mx的距离,超出的部分需要单独计算。
②i>mx:此时,需要逐步往arr[i]两边扩散。

3、扩散结束后,更新mx和id
4、更新maxLength和index(中心位置索引)
5、找出子串

总结

回顾马拉车算法-----
第一步是初始化字符串
第二步得出回文串的长度和p数组的关系:length=p[i]-1
第三步得出回文串的起始索引和p数组的滚关系:start=(i-p[i])/2
第四步开始求p数组,p数组需要分情况讨论。

LeetCode题目

最长回文子串(leetcode-5)

Last modification:March 31st, 2020 at 11:36 pm