转载

manacher算法处理最长的回文子串（一）

引言

相信大家都玩过折叠纸张，如果把回文串相当于折叠一个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算法处理最长的回文子串（一）