最长回文子串算法(Manacher)

Comments: No Comments
Published on: 2012 年 07 月 04 日

算法所求目标为:给出一个字符串,求该字符串最长的回文子串(回文串是左右对称的字符串)。
算法时间复杂度:O(n)。
算法过程:
1、首先先不考虑ABBA这种偶数情况,只考虑ABA这种奇数的情况,下边再说如何考虑偶数的情况。

2、先设置一个record[1-n]数组,用以记录长度为n的字符串的下标位置的最长回文子串的长度。这样可以假设这个记录数组record已经计算出了1-i的所有数据。

3、现在需要计算i+1,i+2,...,i+k的record值,这时候会有如下三种情况:

(1)、 如果record[i-k] < record[i]-k 。因为record[i]是我们已经计算出的回文子串长度,见图中红色线段。record[i-k]也是已经计算出的结果,它是与record[i+k]对称的,所以record[i+k]=record[i-k]。(图中墨绿色箭头为i-k位置的回文子串长度,黑色为字符串string,下同)。

(2)、如果record[i-k] > record[i]-k ,因为record[i]是已经确定了的,而record[i-k]又小于 record[i]-k,所以record[i+k]=record[i]-k,否则的话record[i]应该有更长的长度。

(3)、如果record[i-k]=record[i]-k ,这样record[i+k]至少要大于等于record[i-k],但是我们不能确定应该大多少,这时候我们需要循环比较字符串string[i+k+record[i-k]+j]和string[i+k+record[i-k]-j]是否相同,如果相同就继续扩大j的值进行下轮比较,直到不相同,然后对record[i+k]进行赋值,把下标i跳转到i+k的位置继续循环执行第一步算法直到string比较结束。

(4)、就是关于偶数回文子串的计算了,如果吧"BAAB"转化为"$B#A#A#B?",这样就把偶数的情况转化为了奇数情况,仍然可以执行上诉算法,最后循环一遍record数组即可获取最大回文子串了,或者在计算的过程中就进行记录。

伪代码如下:

fin>>ST;
for (int i=0,End=ST.size(); i!=End; i++){
s[(i<<1)+1]=ST[i];
s[(i<<1)+2]='#';
}
s[0]='?';
s[ST.size()<<1]='*';//注意头,尾和中间插入的字符不同
//前面是初始化
for (int i=1,j=0,k,End=ST.size()<<1; i<End; )
{
while (s[i-j-1]==s[i+j+1]) j++; //扫描得出rad值
rad[i]=j;
for (k=1; k<=j && rad[i-k]!=rad[i]-k; k++) rad[i+k]=min(rad[i-k],rad[i]-k); //k指针扫描
i+=k; //i跳到下一个需要计算rad值的位置
j=max(j-k,0); //更新下一个rad值的初始值
}

 
个人原创,转载请注明:三江小渡

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期五, 2017 年 09 月 22 日