2016年5月

Manacher 算法求最长回文子串

0. 最长回文子串

回文子串是指字符串中顺序读和逆序读都一样的一个子串。给定一个原串,有且仅有一个最长的回文子串,这类问题要求我们将它求出来。直接将字符串和反转后的串一点点比较的话时间复杂度较高,更何况一般都是比较长的字符串,如果能在线性时间内求解的话节约的时间将是相当可观的,Manacher算法就是一种方法。

1. Manacher算法

该算法利用了回文串对称的特点,利用已经知道的信息来减少对比次数。这个信息就是一个数组P(P[i]代表以i为中心的回文串的半径)和记录最长回文子串中点的max(那么max+P[max]就是中点+半径就是已知最长的回文子串的最右一个字符的下标)。

index 0 1 2 3 4 5 6 7 8 9 10 11 12 13
str b a b c b a b c b a c c b a
P[index] 0 1 0 3 0 4 0 2 0 0 0 0 0 0

那么这个数组怎么用呢

比如我们现在要算P[5],且已经知道一个点max是当前已知的最长回文字串的中点,这个子串就是[str[max-P[max]],str[max+P[max]]]这个区间,上例中max=3,str[3-P[3]]到str[3+P[3]]=“babcbab”。此时:

  1. index=5这个字符在这个子串之内,即子串最右的下标为max+P[max]=3+3=6,5<6。那么,既然index=5在子串里,它就可以关于max对称,对称点为index'=1,既然对称,那么关于index'已知的信息就可以拿来用:以index'为中心的回文串长度是P[index']=1是“bab”;还是既然对称,那么以index=5为中心的回文串长度也就至少是1,就是str[index-1]到str[index+1]这一部分,那么在计算以index=5为中心的回文串时,就可以跳过index=5到min(index=5+1,max+P[max])这一部分(取小是因为如果以index=5为中心的回文串长度超出了已知最长的右边界,只能确定5到右边界max+P[max]这一段关于5对称,而不能确定右边界max+P[max]到5为中心的子串的最右是否对称),而从min(index=5+1,max+P[max])+1开始继续匹配。
  2. 如果index > max+P[max],当前位置超出了已知信息的位置,就只能用普通方法地匹配。
  3. 还有个重要的问题,如果字符串长度是偶数,那么在以上过程中就会找不到一个中点的字符。解决方法是在原串每个字符两侧加上同一个特殊符号,要求其在原串中没使用过。这样就可以把偶数长的串都变为奇数长。