最长回文子串 C++

在一个字符串中要到最长的回文子串，有如下方案，代码在最后。

最长回文子串的相关博文

1、暴力法

最容易想到的就是暴力破解，求出每一个子串，之后判断是不是回文，找到最长的那个。

求每一个子串时间复杂度O(N^2)，判断子串是不是回文O(N)，两者是相乘关系，所以时间复杂度为O(N^3)。

2、中心扩展

中心扩展就是把给定的字符串的每一个字母当做中心，向两边扩展，这样来找最长的子回文串。算法复杂度为O(N^2)。
但是要考虑两种情况：
1）长度为奇数。
2）长度为偶数。

3、动态规划
回文字符串的子串也是回文，因此用dpm[i,j]（表示以i开始以j结束的子串）是回文字符串，那么P[i+1,j-1]也是回文字符串。这样最长回文子串就能分解成一系列子问题了。这样需要额外的空间O（N^2)，算法复杂度也是O(N^2)。
首先定义状态方程和转移方程： dpm[i,j]=0表示子串[i,j]不是回文串。dpm[i,j]=1表示子串[i,j]是回文串。

4、Manacher法
Manacher法只能解决例如aba这样长度为奇数的回文串，对于abba这样的不能解决，于是就在里面添加特殊字符。一般添加了“#”，使abba变为a#b#b#a。这个算法就是利用已有回文串的对称性来计算的，具体算法复杂度为O(N)。

Manacher详细介绍

下面是几种方法的代码

inline bool isPalindrome(const string &s,int n1, int n2) {
	for (int k1(n1), k2(n2 - 1); k1 < k2; ++k1, --k2) if (s[k1] != s[k2]) return false;
	return true;
}

string findLongestPalindromeBrute(string s) {
	int sl(s.length()), mlen(1), start(0);
	for (int k1(0); k1 < sl; ++k1) {
		for (int k2(k1 + mlen + 1); k2 < sl; ++k2) {
			if (isPalindrome(s, k1, k2)) start = k1, mlen = k2 - k1;
		}
	}
	return s.substr(start, mlen);
}

string findLongestPalindromeDP(string s) {
	int sl(s.length()), mlen(1), start(0);
	vector<vector<bool>> dpm(sl, vector<bool>(sl, false));
	for (int k1(0); k1 < sl; ++k1) dpm[k1][k1] = true;
	for (int k1(0); k1 < sl - 1; ++k1) {
		if (s[k1] == s[k1 + 1]) {
			dpm[k1][k1 + 1] = true;
			if (!start) start = k1, mlen = 2;
		}
	}
	for (int kn(3); kn <= sl; ++kn) {
		for (int k1(0); k1 <= sl - kn; ++k1) {
			if (dpm[k1 + 1][k1 + kn - 2] && s[k1] == s[k1 + kn - 1]) {
				dpm[k1][k1 + kn - 1] = true;
				mlen = kn;
				start = k1;
			}
		}
	}
	return s.substr(start, mlen);
}

string findLongestPalindromeCE(string s) {
	int sl(s.length()), mlen(1), start(0);
	for (int k1(1), kd(1); k1 < sl; ++k1) {
		for (kd = 1; k1 - kd >= 0 && k1 + kd < sl && s[k1 - kd] == s[k1 + kd];++kd);
		if (mlen < 2 * kd - 1) {
			mlen = 2 * kd - 1;
			start = k1 - kd + 1;
		}
	}
	for (int k1(1), kd; k1 < sl; ++k1) {
		for (kd = 0; k1 - kd >= 0 && k1 + kd + 1 < sl && s[k1 - kd] == s[k1 + kd + 1]; ++kd);
		if (mlen < 2 * kd) {
			mlen = 2 * kd;
			start = k1 - kd + 1;
		}
	}
	return s.substr(start, mlen);
}

string findLongestPalindromeManacher(string s) {
	string s1("$#");
	for (auto ch : s) s1 += ch, s1 += "#";  // Insert '#'
	vector<int> pv(s1.size(), 0);
	int index(0), mlen(1);
	for (int k1(2),mid(1),mxr(0); k1 < s1.size(); ++k1) {
		pv[k1] = k1 < mxr ? min(pv[mid + mid - k1], mxr - k1) : 1;
		while (s1[k1 + pv[k1]] == s1[k1 - pv[k1]]) ++pv[k1];
		if (mxr < k1 + pv[k1]) {
			mxr = k1 + pv[k1];
			mid = k1;
		}
		if (mlen < pv[k1]) {
			mlen = pv[k1];
			index = k1;
		}
	}
	return s.substr((index - mlen) / 2, mlen - 1);
}
string findLongestPalindromeManacher2(string s) {
	string s1("#");
	for (auto ch : s) s1 += ch, s1 += "#";  // Insert '#'
	int sl1(s1.length()), index(0), mlen(1);
	vector<int> pv(sl1, 0);
	for (int k1(1), kd(1), kt; k1 < sl1;) {
		while (0 <= k1 - kd && k1 + kd < sl1 && s1[k1 - kd] == s1[k1 + kd]) ++kd;
		pv[k1] = kd - 1;
		for (kt = 1; kt <= pv[k1] && pv[k1 - kt] < pv[k1] - kt; ++kt) pv[k1 + kt] = pv[k1 - kt];
		k1 += kt;
		kd = kd - kt;
	}
	for (int k1(1); k1 < sl1; ++k1) {
		if (mlen < pv[k1]) {
			mlen = pv[k1];
			index = k1;
		}
	}
	return s.substr((index - mlen) / 2, mlen);
}

其中：

函数isPalindrome 检查一个子串是否为回文子串；

findLongestPalindromeBrute 为暴力方案；

findLongestPalindromeDP 为动态规划；

findLongestPalindromeCE 为中心扩展；

findLongestPalindromeManacher 和 findLongestPalindromeManacher2 为 Manacher方案。