最长回文字符串算法-Manacher’s Algorithm-马拉车算法

时间:2023-01-03 16:47:46

本文翻译于LeetCode上关于最长回文字符串的讲解

除了翻译之外,其中还加入了个人的理解的部分,将其中没有详细说明的部分进行了解释。

时间复杂度为O(n)的算法

首先,我们需要讲输入的字符串 S 进行一下转换得到 T,转换的方法就是通过在每两个字符之间插入一个字符串“#”,你马上就能知道为什么要这么做。

例如 输入字符串 S = “abaaba”, 转换之后得到了 T = “#a#b#a#a#b#a#.

为了找到最长回文字符串,我们的做法是在从T中的第 i 元素开始往字符串的两边进行扩展,例如T[i -d] 到 T[i +d]表示的是以T[i]为中心的回文字符串,你看到这个表示应该就能理解实际上回文字符串的长度是 2 * d.

为了找到最长的回文子串,那么必不可少的就是找出以每个字符为中心的最长回文子串,然后比较之后才能找出最长的。在这里我们使用数组P来保存以T中每个字符为中心的最长回文子串的半径(既长度的一半)。

接着使用上面的例子,
T = # a # b # a # a # b # a #
P = 0 1 0 3 0 1 6 1 0 3 0 1 0

通过查看数组P,找到其中最大的数字,我们可以马上看出最长的回文字符串是”abaaba”.

不知道你是否注意到了我们插入的字符# ,通过插入这个字符,我们可以一次性的处理当输入字符串为奇数或者偶数的情况,而不需要分情况讨论。

不知道你又没有注意一个很重要的事情,那就是观察P中元素,他们是关于中心对称的,不仅仅是这个,在回文串“aba”中,他们在P中对应的数字(1, 3 , 1})也是对称的。这仅仅是一个巧合么?答案可以说是也可以说不是。这种对称的情况仅仅在某种情况下才成立,但是无论如何我们都获得了一个重大的发现。通过这个发现,我们可以减少P中元素的重复计算。

现在让我们来看一个更加复杂的例子,其中包含了一些重叠的回文子串。
S = “babcbabcbaccba”.

最长回文字符串算法-Manacher’s  Algorithm-马拉车算法

上面的图片是从S转换之后得到的T,假设你已经完成了P数组的部分数值的计算,图中的实线表示当前回文串 “abcbabcba”的中心(center C ),两条虚线分别表示以C为中心的回文串的边界。你先需要计算的是 i 的值,图中 i’ 表示的是i 关于 C 对称的点。那么问题来了,怎么计算更有效率的算出P[i] 值。

假设当前 i 的值是 13,我们需要得到 P[13]的值,我们首先看下 i 关于 C对称的 i’ = 9的值。

最长回文字符串算法-Manacher’s  Algorithm-马拉车算法

两条绿色实线覆盖的区域分表表示的是 以 i’ 和 i 为中心的最长回文子串。我们已经知道了 P[i’] = P[9] = 1, 那么非常明显,我们可以推断出 P[i] = P[i’] = 1, 因为回文子串的对称性。(这里稍微解释一下: 因为我们已经知道 a )

正如你在上一段看到的一样,P[i] = P[i’] = 1,这个是由回文子串关于其中心的对称性所决定的。实际上在C之后的三个元素都遵循了这种对称性(既 P[12] = P[10] = 0, P[13] = P[9] =1, P[14] = P[8] = 0 ).

最长回文字符串算法-Manacher’s  Algorithm-马拉车算法

现在我们到了 i = 15 这个点,i 关于 C对称的点是 i’ = 7 ,那么这里 P[15] = P[7] = 7 还会不会成立呢?

很不幸,这个时候如果认为P[15] 那就错了,如果我们以T[15] 为中心开始两边扩展,那么得到的最长回文子串是”a#b#c#b#a”, 这比我们根据对称性所得到的值 7 要小,那么原因是什么?

最长回文字符串算法-Manacher’s  Algorithm-马拉车算法

在上图中,绿色实线表示的是以C为中心的最长回文子串所覆盖的区域,红色实线表示的是与绿色区域不匹配的部分,左边的红色实线是以i’为中心的最长回文子串所覆盖区域超出绿色实线的部分。右边的红色实线是以i为中心的最长回文子串所覆盖区域超出绿色实线的部分。而绿色的虚线部分则是分别以 i 和 i’ 为中心最长回文子串与 绿色实线部分的重叠部分。

从图中我们可以明显的看出被两条绿色实线所覆盖的区域中,C两边的子串是完全相同的。同时绿色虚线的那部分也是关于中心对称的。但是需要注意的是 P[i’] = 7,此时以T[i’]为中心的最长回文子串超出了以C为中心的最长回文子串的左边界(图中L, 左边红色实线),正是因为这个原因,这个时候无法再按照回文子串的对称性来处理了。

现在我们知道的是P[i] >= 5 ,为了找出P[i]最终的值,我们只有继续以P[i]为中心向两边扩展进行比较,在这个例子中P[21] 不等于 P[1],那么我们最终推断是P[i] = 5.

那么总结下来就是下面的伪码

if P[ i’ ] ≤ R – i,
then P[ i ] ← P[ i’ ]
else P[ i ] ≥ P[ i’ ]. (Which we have to expand past the right edge (R) to find P[ i ].

这个表达式是否足够明了,如果你能掌握上面的公式,那么说明你已经知道了这个算法中最精髓也是最难的部分。

接下来的部分就什么时候该去移动当前回文子串的中心C和右边界R的位置,这个相对简单:

如果以i为中心的回文子串的右边界,向右扩展的时候超过了当前的R,那么就将C更新为 i,并且更新R到新的以i为中心的回文子串的右边界。

在每一步中,都存在两种可能,如果P[i’] <= R - i ,我们将P[i]的值设置为P[i],否则我们会尝试以P[i]为中心并且从 R 开始去扩展回文子串,在扩展的过程中最多执行N步,移动和测试每一个中心(P[i])一共需要耗费N步,那么总的时间复杂度是O(n).

下面是Java代码的实现

    private static String preProcess (String s){

int n = s.length();

if (n == 0 ) return "^$" ;

String result = "^" ;

for ( int i = 0 ; i < n; i++) {

result += "#" + s.charAt(i);

}

result += "#$" ;

return result;

}


// the original implementation in C/C++

public static String getLongestPalindrome (String s){

char [] T = preProcess(s).toCharArray();

int n = T.length;

int [] P = new int [n];

int C = 0 , R = 0 ;

for ( int i = 1 ; i < n- 1 ; i++) {

int i_mirror = 2 *C - i; // equals to i' = C - (i-C)

if ( i < R ) {

P[i] = Math.min(R-i, P[i_mirror]);

} else {

P[i] = 0 ;

}

// Attempt to expand palindrome centered at i

while ( T[i+ 1 +P[i]] == T[i- 1 -P[i]] )

P[i]++;

// if palindrome centered at i expand past R

// adjust center based on expanded palindrome

if ( i + P[i] > R) {

C = i;

R = i + P[i];

}

}

int maxLen = 0 ;

int centerIndex = 0 ;

for ( int i = 1 ; i < n- 1 ; i++) {

if (P[i] > maxLen) {

maxLen = P[i];

centerIndex = i;

}

}

int beginIndex = (centerIndex- 1 -maxLen)/ 2 ;

return s.substring(beginIndex, beginIndex+maxLen);

}