鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > erlang > >

《编程之法》1.6最长回文子串

来源:互联网 作者:佚名 时间:2016-07-17 21:11
题目描述:给定一个字符串,求它的最长回文子串(子串是连续的)的长度 解法一:枚举法 外面的双层for循环确定连续子串头尾,加上里面的一个for循环来判断该子串是否为回文串,此外用一个max变量(初始为1)动态更新保存最长子回文串的长度,时间复杂度为O(n^3)

题目描述:给定一个字符串,求它的最长回文子串(子串是连续的)的长度

解法一:枚举法
外面的双层for循环确定连续子串头尾,加上里面的一个for循环来判断该子串是否为回文串,此外用一个max变量(初始值为1)动态更新保存最长子回文串的长度,时间复杂度为O(n^3),空间复杂度为O(1)。

#include <iostream>
#include <string>
using namespace std;
bool IsPalindrome(string &str, int start, int end){
	while(start < end){
		if(str[start] != str[end])
			return false;
		++start;
		--end;
	}
	return true;
}
int LongestPalindrome(string &str){
	if(str.size() == 0)
		return 0;
	int len = str.size(), i, j, maxLen = 1;
	for(i = 0; i < len; ++i){
		for(j = i+1; j < len; ++j){
			if(IsPalindrome(str, i, j))
				if(maxLen < j-i+1)
					maxLen = j-i+1;
		}
	}
	return maxLen;			
}

int main(){
	string str;
	while(cin >> str){
		cout << LongestPalindrome(str) << endl;
	}
	return 0;
}

解法二:中心扩展法
一个for循环将字符串中的每个元素作为中心点,并对该中心点是奇数回文串中心还是偶数回文串中心分开写程序,在该中心点位置上进行扩展,依次比较两边的对应元素是否相等,时间复杂度为O(n)*O(n/2+n/2)=O(n^2),程序代码如下:

#include <iostream>
#include <string>
using namespace std;
int LongestPalindrome(string &str){
	if(str.size() == 0)
		return 0;
	int i, j, maxLen=1;
	for(i = 0; i < str.size(); ++i){
		//该点为奇数字符数的回文串中心
		for(j = 0; i-j >= 0 && i+j <= str.size()-1; ++j){
			if(str[i-j] != str[i+j])
				break;
		}
		if(maxLen < 2*(j-1) + 1) //注意跳出的j的取值,如asdsf,j=2时跳出,而最长回文子串为:2*(j-1)
			maxLen = 2*(j-1) + 1;
		//该点为偶数数字符数的回文串中心
		for(j = 0; i-j>=0 && i+j+1 <= str.size()-1; ++j){
			if(str[i-j] != str[i+j+1])
				break;
		}
		if(maxLen < 2*(j-1) + 2)
			maxLen = 2*(j-1) + 2;
	}
	return maxLen;			
}

int main(){
	string str;
	while(cin >> str){
		cout << LongestPalindrome(str) << endl;
	}
	return 0;
}


解法三:Manacher算法

步骤如下:
a,像下面这样对字符串12212321进行插字符
S[i]:*#1#2#2#1#2#3#2#1#
P[i]: 12125214121612121
即先在原字符串中每个字符左右插字符#,最后在最前面插字符*。P[i]是以该字符为中心的最长回文子串的右半边长度(含中心本身)。插入*可以更好的处理越界问题,字符间插入#是为了使所有回文子串都变为奇数,这样无需像中心扩展法那样还要考虑偶数的问题。


b,接下来是如何求P[i]
这就像动态规划一样,先求P[0],再求P[1],再由P[0]和P[1]求P[2],...,再由P[0]~P[i-1]求P[i],...。我们以前用到动态规划时,如求两字符串的最长公共子串,根据dp[i-1][j-1],dp[i][j-1],dp[i-1][j]来求dp[i][j],故我们需要确定P[i]的来源。而在Manacher算法中P[i]的来源有两种,一是若P[i]关于id(下一句解释id含义)与P[j]对称,那么P[i]可由P[j]求出,二是无法使用前面的P[j]时,直接依次比较S[i]两边的元素是否相等。
由于之前已经知道以S[1]~S[i-1]为中心的最大回文串长,此时定义两个变量mx和id,mx指S[1]~S[i-1]为中心的所有最长回文子串中能延伸到的最右端的位置,且是以S[id]为中心的,故mx = id + P[id]。故mx为以id为中心的回文子串右半段的下一个位置(不在回文串内)。
由此时,分两种大情况:
1,若mx<=i,此时无法使用S[id]为中心来求得S[i],只能以它为中心依次判断两边元素是否相等。代码将P[i]当成i,这样写,P[i]=1;while(S[i+p[i] == S[i-P[i]) ++P[i];

2,若mx>i,以以下三种情况进行分析:
A, 如下图,S[2*id-i]的回文子串完全在S[id]的回文子串范围时,则根据对称性,P[i] = P[2*id-i]。
P[i]不可能比这大或比这小,假设P[i]比P[2*id-i]大,如多出如下的1和2部分,由于该范围是关于id对称的,最后也会得出P[2*id-i]应该变大,多出3和4部分,矛盾;若假设比它小也会产生相似的矛盾。故P[i] = P[2*id-i]。


B,如下图,S[2*id-i]的回文子串的左半边等于id的左侧范围的最左侧位置,而下面黑色部分1与红色部分2不同,两个红色部分2,3对称相等,而蓝色部分4有可能与红色部分3相同,故先令P[i]=mx-i; 再while(S[i+p[i] == S[i-P[i]) ++P[i];


C,如下图,S[2*id-i]的回文子串的左半边超过id的左侧范围,故此时P[i]=mx-i。不可能更长了,假设更长,及下面的部分1和部分2相等,而部分2和部分3关于id对称相等,而部分3和部分4关于2*id-i对称相等,故部分1和部分4相等,进而推出id的范围超过了绿色范围,矛盾。


对于2中的情况A和情况C,令P[i] = P[2*id-i]后, 再执行while(S[i+p[i] == S[i-P[i]) ++P[i];也不会对结果有什么影响,因为肯定不满足条件而无法进入while中处理,S[i]依然等于S[2*id-i]。
故核心代码为:

if(mx > i) P[i] = min(P[2*id-i], mx-i);
else P[i] = 1;
while(S[i+p[i] == S[i-P[i]) ++P[i];


c, 接下来是重新放置id的位置,只需比较i和旧的id谁能向右边延伸最远。

完整算法代码如下:

#include <iostream>
#include <string>
#define max 110
using namespace std;
int P[2*max + 2];
int Manacher(char *S){
	int i, len = strlen(S);
	for(i = len-1 ; i >= 0; --i){
		S[2*i + 2] = S[i];
		S[2*i + 1] = '*';
	}
	S[0] = '$';
	S[2*len + 1] = '*';
	S[2*len + 2] = '\0';//最后需要加'\0',避免越界
	int id = 0, maxLen = 0;
	P[0] = 1;
	for(i = 1; i <= 2*len+1; ++i){
		if(i < P[id] + id)
			P[i] = min(P[2*id - i], P[id] + id - i);
		else
			P[i] = 1;
		while(S[i + P[i]] == S[i - P[i]])
			++P[i];
		if(P[i] + i > P[id] + id)
			id = i;
		if(P[i] > maxLen)
			maxLen = P[i];
	}
	return maxLen-1;

}

int main(){
	char S[2*max + 2];
	while(cin >> S){
		cout << Manacher(S) << endl;
	}
	return 0;
}
总结:Manacher算法的时间复杂度一般为O(n),但我认为它的时间复杂度应该比O(n)要大。该算法和中心扩展法差不多,依次从下标1开始从小到大来分别计算以该点为中心的最长回文子串,每次遍历时,如果可以利用到S[id*2-i]就能省去P[id*2-i]次比较,如果不能利用则还是需要以该中心点依次比较它两边的元素。

举一反三:

输出最长回文子串:将一个很长的字符串分割成一段一段的子串,要求子串都是回文串,且每次输出最长的回文串。如输入"habbafgh",输出"h","abba","f","g","h"。
可以使用中心扩展法将所有回文子串输出,可能考虑到输出不能重复的问题,可设置vecter<string>来对每次输出时进行比较。
也可用曼彻斯特算法根据得到的p[]将所有的子回文串输出,设置vector<string>来解决输出重复问题。

网友评论
<