manacher算法处理最长的回文子串(一)

时间:2022-07-06 01:32:15

引言

相信大家都玩过折叠纸张,如果把回文串相当于折叠一个A4纸,比如ABCDDCBA就是沿着中轴线(D与D之间)对折重合,那么这个就是一个回文串。或者是ABCDEDCBA的中轴线就是E,那么沿着中轴线对折也是重合的,所以这个字符串也是一个回文串。

   判断一个字符串中的最长回文子串,我们可以对每个字符的两边进行比较,还是如何ABCDEDCBA,在A,B,C,D分别为中心轴向两边扩展的回文子串长度都是1,就是它自己本身,当扫描以E为中心轴时,那么这个回文的最长子串时9,也就是这个字符串本身。然而当用相同的方法处理ABCDDCBA时,分别以A,B,C,D为中心轴向两边扩展,得到的最长回文子串的长度是1,实际上最长的回文子串却是ABCDDCBA,就是它自己本身。

  为了解决以上的问题,我们对原来的子串就行填充,比如用'#'来填充,其实任意字符都是可以的。这样原来为N长度的字符串变成了2*N+1的长度。例如ABCDDCBA为例子,填充完新的字符串为#A#B#C#D#D#C#B#A#。这样根据刚才的方法从左往右,以每个字符为中心轴扩展。得到以第5个'#'为中心轴,向两边扩展扫描时,这个回文子串为最大回文子串,即本身。最大回文长度为2*8+1=17,那么原来的最大回文子串长度为17/2=8。

  以上的方法,每次都要以每个字符为中心轴向两边扩展,且扩展长队为1,2,...N/2,则平均时间负责度为O(n^2)。

原理

      1)现在如下图所示,现在已知以idx为中心轴的回文子串的长度为花括号括起来,则现在求以i为中心抽的回文子串长度,首先保证i处于以idx为中心轴的回文串中。那么i的以idx的对称点是i',且i'的回文子串的长度也已知(用括号括起),其中i指向c,i'指向b。(本文的小写字母都是变量,大写字母规定为具体字符)

那么由e为中心的回文子串中得知,b=c。又因为idx的回文不包括a和d,那么a!=d,否则a=d时,以idx的回文子串还要扩展下去。由因为idx左 到b 和 idx右到c 相等的。有因为a!=d,所以以c为中心轴的回文半径只有idx右-location(c)。因为若a关于以b为中心的回文的对称点为a'。a'以e为中心轴的回文的对称点为a''。那么a=a'=a''!=b。

manacher算法处理最长的回文子串(一)

以下面的例子说明

manacher算法处理最长的回文子串(一)

以9号D为中心轴的回文子串的长度为16-2+1=15。他是从2号开始,16号结束。现在也知道以5号B为中心轴的回文子串长度是10-0+1=11。那么13号B的对称点就是5号的B。那么以13号B为中心轴的回文长度是多少?1号D和17号E不相等。现在只要判定以13号B为中心抽的回文子串是否包括17号。若包括17号E,那么它的对称点9号。且9号的对称点是1号D,那么可知17号应该等于9号等于1号,实际上可知1号和17号不相等。所以以13号为中心抽的回文不包括17号E。有根据以5号和9号为中心的回文串可知  2号--5号 ,8号--5号, 10号--13号  16号--13号 都是相等的。

2)下面是第二种情况,若i'的回文串的直径被idx的回文串包含的话。如下图。

manacher算法处理最长的回文子串(一)

已知i关于idx为中心轴的对称点i'的最大回文子串如上图。因为i'的回文子串不包括a,b则a!=b,有因为a,d和b,c分别关于idx对称,记b=c,a=d。所以c!=d。又因为在c和d之间是回文,原因在于c和d之间的字符关于idx的a和b之间对称,且a和b之间是回文串,所以,c和d之间也是回文串。所以i的回文串串的长度和i'相同。例子如下:

manacher算法处理最长的回文子串(一)

3)下面是第三种情况,若i'的回文左边界与idx的回文左边界重合时,如下图。

manacher算法处理最长的回文子串(一)

由idx为中心抽的回文串可知,b=c,a!=d。且i'的回文长度在a到b之间(不包括a,b)。那么i的回文串的长度至少如上图所示。若c=d时,关于i为中心轴的回文还是可以扩展的。若c!=d则刚好是上图所示的括号内。例子如下。(是c=d的这种情况)

manacher算法处理最长的回文子串(一)

i关于idx的对称点i'的最长回文子串如上图,且i'的回文左边界与idx重合,所以i为中心的回文需要充阴影边界开始在往左右两边试着扩展。

  4)第四种情况,就是当i没有被idx为中心的回文包含时,那么我们没有任何信息可以利用,只能以i为中心轴,向左右两边扩展。找出它的最长回文子串。

manacher算法处理最长的回文子串(一)

manacher算法的原理如上所示,代码将在下章给出。