OJ刷题----[算法课动态规划]最长回文子串（C++完整代码）_problem p09. [算法课动态规划]最长回文子串 求一个字符串中的最长的回文子串

题目：

求一个字符串中的最长的回文子串

输入：

求一个字符串中的最长的回文子串

输出：

输出最长的回文子串

完整代码（C++）：

方法一：

#include<iostream>
#include<vector>
#include<string>
using namespace std;

class Solution {
public:
	string longest(string s) 
	{
		if (s.size() == 0) return s;
		int size = s.size(); 
		vector<vector<int>> dp(size, vector<int>(size));
		string ret = "";
		int max = 0;
		for (int i = 0; i < size; i++) 
		{
			for (int j = 0; j <= i; j++)
			{
				dp[i][j] = s[i] == s[j] && (i - j <= 2 || dp[i - 1][j + 1]);
				if (dp[i][j])
				{
					if (i - j + 1>max) {
						max = i - j + 1;
						ret = s.substr(j, i -j + 1);
					}
				}
			}
		}
		return ret;
	}
};

int main()
{
	Solution sol;
	string s;
	cin >> s;
	cout << sol.longest(s) << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

方法二：

#include<iostream>
#include<vector>
using namespace std;
class Solution
{
public:
	string longest(string s)
	{
		if (s.size() < 2) return s;
		int length = s.size();
		vector<vector<bool>> f(length, vector<bool>(length));
		int maxlength = 1;
		int begin = 0;
		for (int i = 0; i < length; i++)
		{
			f[i][i] = true;
		}
		for (int j = 1; j < length; j++)
		{
			for (int i = 0; i < j; i++)
			{
				if (s[i] != s[j]) f[i][j] = false;
				else
				{
					if (j - i < 3)
					{
						f[i][j] = true;
					}
					else
					{
						f[i][j] = f[i + 1][j - 1];
					}
				}
				if (f[i][j] && (j - i + 1) > maxlength)
				{
					maxlength = j - i + 1;
					begin = i;
				}
			}
		}
		return s.substr(begin, maxlength);
	}
};
int main()
{
	Solution sol;
	string s;
	cin >> s;
	cout << sol.longest(s) << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

学习链接：最长回文子串学习链接

输出