5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

这题要求我们找出一个字符串S中的最长回文子串，之前在hihoCoder 1032-最长回文子串就详细讨论过相关问题，这里就不再赘述了，代码完全一样，如下：

class Solution {
public:
	string preProcess(string s)
	{
		int n = s.size();
		if (n == 0)
			return "^#";
		string ret = "^";
		for (int i = 0; i < n; i++)
			ret += "#" + s.substr(i, 1);
		return ret + "#$";
	}
	string longestPalindrome(string s) {
		string t = preProcess(s);
		vector<int> p(t.size(), 0);
		int c = 0, r = 0, n = t.size();
		for (int i = 1; i < n - 1; i++)
		{
			int i_mirror = 2 * c - i;
			p[i] = (r > i) ? min(p[i_mirror], r - i) : 0;
			while (t[i + p[i] + 1] == t[i - p[i] - 1])
				p[i]++;
			if (i + p[i] > r)
			{
				c = i;
				r = i + p[i];
			}
		}
		
		int maxLen = 0, centerIndex = 0;
		for (int i = 1; i < n - 1; i++)
		{
			if (p[i] > maxLen)
			{
				maxLen = p[i];
				centerIndex = i;
			}
		}
		
		return s.substr((centerIndex - 1 - maxLen) / 2, maxLen);
	}
};

本代码提交AC，用时12MS，击败了73%的CPP用户，看来效率不错，估计中心扩展法$O(n^2)$也能过。

二刷。上面的Manacher’s算法过于小众，咱们还是来点大众算法吧，容易理解和记忆。

首先是DP方法，设dp[i][j]=1表示s[i:j]形成回文，=0表示不是回文。则如果s[i:j]形成回文，且s[i-1]==s[j+1]，则可以在s[i:j]的基础上进一步扩展，使得s[i-1:j+1]也是回文，即dp[i-1][j+1]=1。

稍微要注意的是DP的时候，第一层循环是子串的长度，因为我们是在短的子串上看起周围2个字符是否相等，所以先要求出短的dp[i][j]，再求长的dp[i-1][j+1]。

完整代码如下：

class Solution {
public:
	string longestPalindrome(string s) {
		int n = s.size();
		if (n == 0)return "";
		vector<vector<int>> dp(n, vector<int>(n, 0));
		int ans = 1, u = 0, v = 0;
		for (int len = 0; len < n; ++len) {
			for (int i = 0; i < n; ++i) {
				int j = i + len;
				if (j >= n)break;

				if (len == 0)dp[i][j] = 1;
				else if (len == 1) {
					if (s[i] == s[j]) {
						dp[i][j] = 1;
						if (2 > ans) {
							ans = 2;
							u = i;
							v = j;
						}
					}
				}
				else {
					if (dp[i + 1][j - 1] == 1 && s[i] == s[j]) {
						dp[i][j] = 1;
						if (j - i + 1 > ans) {
							ans = j - i + 1;
							u = i;
							v = j;
						}
					}
				}
			}
		}
		return s.substr(u, v - u + 1);
	}
};

本代码提交AC，用时184MS。

还有一种中心扩展法也很好理解，即假设每个字符是回文的中心字符，然后看看两端字符是否相等，如果相等的话，则继续扩展。需要注意的是，回文有两种形式，一种是aba，即中心只有一个字符，且总长度是奇数；另一种是abba，即中心有两个字符，且总长度是偶数。这种解法相比于上一种解法，只需要O(1)的空间复杂度。

完整代码如下：

class Solution {
public:
	int expand(string &s, int l, int r) {
		int n = s.size();
		while (l >= 0 && r < n&&s[l] == s[r]) {
			--l;
			++r;
		}
		return r - l - 1;
	}
	string longestPalindrome(string s) {
		if (s.size() == 0)return "";
		string ans = "";
		for (int i = 0; i < s.size(); ++i) {
			int len1= expand(s, i, i);
			int len2= expand(s, i, i + 1);
			if (len1 > len2&&len1 > ans.size()) {
				ans = s.substr(i - len1 / 2, len1);
			}
			if (len2 > len1&&len2 > ans.size()) {
				ans = s.substr(i - len2 / 2 + 1, len2);
			}
		}
		return ans;
	}
};

本代码提交AC，用时20MS。