给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s = "abcba";
int strlen = s.size();
vector<vector<int>> dp(strlen, vector<int>(strlen));
vector<string> strOut;
/* 初始化 */
int left, right;
int maxSubStrLen = 0;
for (int i = 0; i < strlen-1; i++)
{
dp[i][i] = 1;
if (s[i] == s[i+1])
{
dp[i][i+1] = 1;
}
}
int i, j;
for (j = 0; j < strlen; j++)
{
for (i = j; i >= 0; i--)
{
if ((s[i] == s[j]) && ((j-i<=2) || (1 == dp[i+1][j-1])))
{
dp[i][j] = 1;
if (maxSubStrLen < j-i)
{
maxSubStrLen = j-i;
left = i;
}
}
else
{
dp[i][j] = 0;
}
}
}
strOut.push_back(s.substr(left, maxSubStrLen+1));
cout << strOut[0] << endl;
return 0;
}
