如何求最长回文子串

如何求最长回文子串回文字符串,就是像“12321”这种轴对称形式的字符串,系不系很简单呀(狗头)。但并不是所有的字符串都是这种整个串都是回文串的。有些计算机问题就是在一个字符串中找出一段最长的回文字符子串,这个时候时候,我们会很自然的想到一种暴力的方法来解决。1975年,一位叫Manacher的人发明了一个算法,这个算法是用来查找一个字符串的最长回文子串的方法。…

大家好,又见面了,我是你们的朋友全栈君。

前言

回文字符串,就是像“12321”这种轴对称形式的字符串。
但并不是所有的字符串都是这种整个串都是回文串的,比如1232。有些计算机问题就是在一个字符串中找出一段最长的回文字符子串,这个时候时候,我们就需要一些算法来求出结构。

方法一:暴力求解
char str[10]={ 
   "5234331"};
	int len=strlen(str),max=0;
	for(int i=0;i<len;i++){ 
   
		int res=1,j=1;
		while(i-j>=0&&i+j<len-1&&str[i-j]==str[i+j]) { 
   res+=2;j++;}
		if(res>max) max=res;
	}
	printf("%d",max);

这种做法就是对每一个字符,匹配它左右两边的字符,如果相同,则res+=2,最后取最大值max。
时间复杂度达到了O(n2),当字符长度到10000时,程序的效率就不行了,时间复杂度太高。
而且这种方法还要判断长度的奇偶性(上面只是判断奇数,在这里就不多说了),代码比较长。

方法二:Manacher算法

时间复杂度由O(n2)缩短为O(n),运行效率提高了很多(tql)。
1. 变换
既然回文字符串有奇偶之分,分奇偶的话,程序将会很复杂,那么我们就要想办法避免这种情况。随便选两个不同的字符串,比如”123324″,“123432”,这两个字符串的最长回文子串奇偶性都不同。那么我们选一个字符串中没出现的字符(如#),将其插入到上面的字符串每个字符的左右两边,变成如下形式
#1#2#3#3#2#4#
#1#2#3#2#3#2#
这样回文子串长度都变成了奇数,有利于计算(舒服)。
处理一个字符串S之后,我们在利用一个和S等长的数组L,其中L[ i ]表示以S[ i ]为中心的回文串的半径,如下:
212321
# 2 # 1 # 2 # 3 # 2 # 1 #
1 2 1 4 1 2 1 6 1 4 1 2 1

仔细观察上面的式子,发现以‘3’为中心的回文串半径为6,而对应的回文串“12321”长度为5,以‘1’为中心的回文串的半径为4,而对应的回文串“212”长度为3,规律很快就找到了:回文串的长度等于半径-1。所以我们只需要找出最大的半径就可以找出最长的回文串的长度。但是如果想要定位最长回文子串的位置,我们还需要知道字符串的起始位置。
我们来看“12321”这个回文子串,它的中间字符‘3’在改变后的字符串中的位置为7,它的半径为6,7-6=1,这样发现,字符串“12321”在原字符串中的位置就是1。再来看“212”这个字符串,他的中间字符位置和半径分别为3和4,但是3-4=-1,起始位置变成负数了,这样是不行的。所以我们这时在字符串的首位添加一个特殊的字符。
比如‘&’,字符串变成:
& # 2 # 1 # 2 # 3 # 2 # 1 #
1 1 2 1 4 1 2 1 6 1 4 1 2 1

(下标从零开始)
这样做仅仅只是把字符串往后移一位,没有做出过多改变,但是带来的收益却很大。
再来看“212”这个字符串,它的中间字符位置变为,4,半径为4,这样一减等于0,没有出现负数,而且在原字符串中的起始位置也为0,感觉可以,再来看“12321”,它的中间字符位置变为8,半径为6,一减等于2,除以2等于1,它在原字符串中的起始位置也为1,这样和上面的例子结合起来,发现添加‘&’后:
( 中间字符的位置-半径 ) / 2=在原字符串中的起始位置
由上面的推导,我们得出算法的规律,现在就差代码实现了。
2. 计算
现在需要的就是如何求出半径数组L[ i ]。设idmx分别为最接近字符尾的回文子串的中点位置和右端位置。那么整个核心算法如下:
L[i]=mx>i?min(L[2*id-i],mx-i):1;
当mx>i,则L[ i ]=min( L[2 * id – i] , mx-i),否则L[ i ]=1。
在这里插入图片描述如上图:

  1. 当mx-i>L[ j ]的时候,以S[ id ]为中心的回文子串包含以S[ j ]为中心的回文子串,由于 i 和 j 对称且id左右两边对称,所以以S[ id ]为中心的回文子串必然也包含以S[ j ]为中心的回文子串,见上图,所以有L[ i ]=L[ j ],其中 j = id * 2-i 。
    在这里插入图片描述
  2. 当mx-i<L[ j ]的时候,以S[ id ]为中心的回文子串不一定完全包含以S[ j ]为中心的回文子串,但由于对称性可知,L[ i ]和L[ j ]在绿线以内的部分是相同的,但是到mx之外的部分需要额外取匹配
  3. 当i>mx时,因为i已经超过mx了,所以找不到对称点,只能额外匹配了。
    通过上面的过程可以得出一个最长回文子串,下面给出代码
#include<bits/stdc++.h>
using namespace std;
int main(){ 
   
	string s,t("!#");
	getline(cin,s);
	//将s化成 !#a#b#c#b#c 这种形式
	//其目的是让奇数和偶数的情况相同
	//方便下面的最长回文串的计算 
	for(int i=0;i<s.size();i++){ 
   
		t+=s[i];
		t+='#';
	}
	vector<int> p(t.size(),0);
	int mx=0,id=0,resl=0,resc=0;
	//mx为回文串最右端
	//id为能达到最右端的回文串的中间 
	//resl为最大的回文串的半径
	//resc为最长的回文串的中间位置 
	for(int i=1;i<t.size();i++){ 
   
		//马拉车的核心算法 //判断以t[i]为中心的回文串长度 
		p[i]=mx>i?min(p[2*id-i],mx-i):1;
		//额外匹配的部分 
		while(t[i-p[i]]==t[i+p[i]]) ++p[i];
		if(mx<i+p[i]){ 
   
			mx=p[i]+i;
			id=i;
		}
		//保留最长的部分 
		if(resl<p[i]){ 
   
			resl=p[i];
			resc=i;
		}
	}
	/*最长的回文串的范围为 (最长的回文串的中间位置-最长的回文串的半径)/2的位置 到 (最长的回文串的半径-1)的位置 */ 
	cout << s.substr((resc-resl)/2,resl-1);
	return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/140935.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号