回文是指正着读和倒着读，结果相同，比如abcba或abba，题目是要在一个字符串中要到最长的回文子串

首先我们可以考虑一般的情况，先从字符串中取出任意一个子串，判断其是不是回文字符串，这种方法可以称之为暴力求解法，故时间复杂度可以达到o(n³)

代码如下所示：

import java.util.*; public class Palindrome {    //判断回文的函数    public boolean isHuiWen(String A, int n){        int k = n / 2;        for (int i = 0; i < k; ++i)        {            if (A.charAt(i) != A.charAt(n-1-i))                return false;        }        return true;    }    public int getLongestPalindrome(String A, int n)     {        int maxlen=0;        for(int i=0 ;i< n ;i++)        {            for(int j=i+1 ;j<=n ;j++)            {                //两层循环遍历出所有的子串，并且逐一判断是否是回文                if(isHuiWen(A.substring(i, j),j-i))                {                    if(j-i>maxlen)                        maxlen=j-i;                }            }        }        return maxlen;    }}

当然我们也可以使用时间复杂度低一点的方法，譬如使用动态规划求解，回文字符串的子串也是回文，比如P[i,j]（表示以i开始以j结束的子串）是回文字符串，那么P[i+1,j-1]也是回文字符串。这样最长回文子串就能分解成一系列子问题了。这样需要额外的空间O（N^2)，算法复杂度也是O(N^2)。

首先定义状态方程和转移方程：

P[i,j]=0表示子串[i,j]不是回文串。P[i,j]=1表示子串[i,j]是回文串。

string findLongestPalindrome(string &s)  {      const int length=s.size();      int maxlength=0;      int start;      bool P[50][50]={
   false};      for(int i=0;i
     
      =2)          return s.substr(start,maxlength);      return NULL;  }