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.
给定一个字符串s，找到s中最长的回文子字符串。您可以假设s的最大长度为1000
Example:

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

Example:

Input: "cbbd"
Output: "bb"

回文的含义是：正着看和倒着看相同，如abba和yyxyy。

使用的是动态规划的方法，从边界值入手，即递归的逆过程，先求字符串最后两个字符是否为回文，一步步递推到整个字符串。

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

int maxLen[10001][10001];   //字符串长度限制1000
class Solution {
public:
    string longestPalindrome(string s) {
        int i, j,start=0, maxNum = 1;   //定义初始位置为0，最小长度为1；
        int len = s.length();
        string temp;
        //初始化，将矩阵对角线初始化为1，一个字符是回文
        for (i = 1; i <= len; i++)
        {
            for (j = 1; j <= len; j++)
            {
                maxLen[i][j] = 0;
            }
            maxLen[i][i] = 1;
        }
        //如果长度为1或者为空，返回
        if (len == 1|| len == 0){
            return s;
        }
        //遍历
        for (i = len - 1; i > 0; i--)
        {
            for (j = i + 1; j <= len; j++)
            {
                if (s[i - 1] == s[j - 1]){//如果字符串为回文，两边相同，回文长度为中间字符串+2
                    maxLen[i][j] = maxLen[i + 1][j - 1] + 2;
                    if ((maxLen[i][j] > maxNum)&&maxLen[i][j]==j-i+1)       //一个回文字符串的长度等于矩阵下标之差即字符串的下标之差加一
                    {
                        maxNum = maxLen[i][j];
                        start = i-1;    //以一开头，所以减去1
                    }
                }
            }
        }
        //输出矩阵
        for (i = 0; i <= len; i++)
        {
            for (j = 0; j <= len; j++)
            {
                cout << maxLen[i][j] << " ";
            }
            cout << endl;
        }
        //回文字符串长度为矩阵最大值
        temp = s.substr(start, maxNum);

        cout << "a:  "<<start<<"  maxnum:  "<<maxNum<<"  string: " << temp << endl;
        return temp;
    }

};

int main(){
    Solution s;
    string str;
while (cin >> str){
        str = s.longestPalindrome(str);
        cout << "str: " << str << endl;
        }
}

【相关文档】
1.最长回文子串