[LeetCode]Longest Palindromic Substring

求出所有的回文，从中找出最长。两种做法。首先是DP，用DP[i][j]表示s[i, j]是否为回文。我们有递推公式：

• DP[i][j] = true, if (DP[i + 1][j - 1] == true || j - i > 2) && s[i] == s[j]
• otherwise, DP[i][j] = false

时间复杂度空间复杂度都为O(n^2)，代码如下：

	class Solution {
	public:
	string longestPalindrome(string s) {
	int len = s.size();
	string res = "";
	vector<vector<bool>> isPalin(len, vector<bool>(len, false));
	for(int i = 0; i < len; ++i)
	{
	for(int j = 0; j <= i; ++j)
	{
	if(s[i] == s[j] && (i - j < 2 || isPalin[j + 1][i - 1]))
	{
	isPalin[j][i] = true;
	if(i - j + 1 > res.size())
	res = s.substr(j, i - j + 1);
	}
	}
	}
	return res;
	}
	};

view raw Longest Palindromic Substring_II.cpp hosted with ❤ by GitHub

第二种就是从每一个字符开始向两边展开，直到不是回文为止。常数空间，时间复杂度worst case O(n^2)，但是我们有剪枝，所以正常情况是比它快的。代码如下：

	class Solution {
	public:
	string longestPalindrome(string s) {
	int len = s.size();
	string res = "";
	for(int i = 0; i < len; ++i)
	{
	//odd length
	for(int j = 0; i - j >= 0 && i + j < len && s[i - j] == s[i + j]; ++j)
	if(2 * j + 1 > res.size())
	res = s.substr(i - j, 2 * j + 1);
	//even length
	for(int j = 0; i - j >= 0 && i + j + 1 < len && s[i - j] == s[i + j + 1]; ++j)
	if(2 * j + 2 > res.size())
	res = s.substr(i - j, 2 * j + 2);
	}
	return res;
	}
	};

view raw Longest Palindromic Substring_I.cpp hosted with ❤ by GitHub

最后我们介绍一个线性时间求最长回文子串的算法，manacher算法。对于string s我们首先做预处理，将其每一个字符中间插入一个特殊字符，比如#。例如s为aacaa的情况，预处理之后就变为#a#a#c#a#a#，处理完之后有一个好处，就是在原字符串中长度为奇数和偶数回文串，在新字符串中长度都为奇数。比如aa变为#a#a#，aacaa变为#a#a#c#a#a#。如此一来，我们只需要在新字符串中找到奇数长度最长回文串即可。为了在线性时间找到最长的奇数长度的回文串，我们用r[i]记录以i位置为中心的回文的最长半径，最小为1。此外，我们用maxRight和maxPos记录已经扫过的i中，以maxPos为中心的回文是向右延伸到最远的，一直到maxRight。那么我们有几种情况，第一种是当前我们所在位置i < maxRight，如图所示：

那么我们可以找到i关于maxPos的对称点j = 2* maxPos - i，因为i永远是在maxPos右边的，所以对称点一定在i的左边。由于j的信息我们是已经知道了的。假设r[j] = k，有以下两种情况：

1. k < maxRight - maxPos + 1，那么由于i和j是在以maxPos为中心的回文中完全对称的，所以以i为中心的回文的半径，不可能超过k，因为i + k + 1和i - k - 1处的字符左右不match，j + k + 1和j - k - 1的结论的镜像。
2. k >= maxRight - maxPos + 1, i处最长回文的右端点已经到达maxRight，其还能够多长我们也不知道，因为没有足够的信息，所以我们继续match。j的结论最多只作用到maxRight，因为超过maxRight之后，对称性消失了，我们只能一个一个match来确认最长的。

假设i >= maxRight，我们没有足够的信息，初始r[i]为1，一个一个匹配。代码如下：

	class Solution {
	public:
	string longestPalindrome(string s) {
	string t = "#";
	for (auto& c : s)
	{
	t += string(1, c);
	t += "#";
	}
	//border guard
	t = "#" + t + "$";
	int len = t.size(), maxP = -1, rBound = -1, resP = -1, resR = 0;
	vector<int> r(len, 0);
	for (int i = 1; i < len - 1; ++i)
	{
	r[i] = rBound > i? min(r[2 * maxP - i], rBound - i + 1): 1;
	while (t[i + r[i]] == t[i - r[i]])++r[i];
	if (i + r[i] - 1 > rBound)
	{
	rBound = i + r[i] - 1;
	maxP = i;
	}
	if (r[i] > resR)
	{
	resR = r[i];
	resP = i;
	}
	}
	return s.substr((resP - 1) / 2 - (resR + 1) / 2 + 1, resR - 1);
	}
	};

view raw Longest Palindromic Substring_manacher.cpp hosted with ❤ by GitHub

时间复杂度就等于maxRight的向右移动的速度，因为处于maxRight左边的所有字符我们只会匹配一次，如果右边的字符被匹配了，maxRight就会向右扩张。很明显这个是线性的。