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

1.蛮力法（Brute Force）

最容易想到的就是暴力破解，求出每一个子串，之后判断是不是回文，找到最长的那个。求每一个子串时间复杂度 O(N^2)，判断子串是不是回文 O(N)，两者是相乘关系，所以时间复杂度为 O(N^3)。

string longestpalindrome(string s) {    int length = s.size();//字符串长度      int maxlength = 0;//最长回文字符串长度      int start;//最长回文字符串起始地址      for(int i = 0;i < length;i++)//起始地址          for(int j = i+1;j < length;j++) {       //结束地址              int tmp1,tmp2;              for(tmp1 = i,tmp2 = j;tmp1 < tmp2;tmp1++,tmp2--) {  //判断是不是回文                  if(s.at(tmp1) != s.at(tmp2))                      break;              }              if(tmp1 >= tmp2 && j-i > maxlength) {                maxlength = j-i+1;                  start = i;              }          }          if(maxlength > 0)              return s.substr(start,maxlength);//求子串          return NULL;}复制代码

2.动态规划法（Dynamic programming）

回文字符串的子串也是回文，比如 p[i,j]（表示以i开始以j结束的子串）是回文字符串，那么 p[i+1,j-1] 也是回文字符串。这样最长回文子串就能分解成一系列子问题了。这样需要额外的空间 O(N^2)，算法复杂度也是 O(N^2)。

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

p[i,j] = false 表示子串 [i,j] 不是回文串。p[i,j] = true 表示子串 [i,j] 是回文串。复制代码

代码如下：

string longestpalindrome(string s) {    int length = s.size();      int maxlength = 0;      int start;      bool p[50][50] = {false};      for(int i = 0;i < length;i++) {     //初始化准备           p[i][i] = true;          if(i < length - 1 && s.at(i) == s.at(i+1)) {              p[i][i+1] = true;              start = i;              maxlength = 2;          }      }      for(int len = 3;len <= length;len++) {   //子串长度          for(int i = 0;i <= length - len;i++) {      //子串起始地址              int j = i+len-1;//子串结束地址              if(p[i+1][j-1] && s.at(i) == s.at(j)) {                p[i][j] = true;                  maxlength = len;                  start = i;              }          }         }    if(maxlength > 0)          return s.substr(start,maxlength);      return NULL;}复制代码

以下方法无需讨论串长度的奇偶性，列举回文串的起点或者终点来解最长回文串问题，看下面代码容易理解：

string longestPalindrome(string s) {	int length = s.size();	bool p[50][50] = {false};  	int start;  	//p[i][j] 表示s[i...j]是否是回文串  	int maxlength = 0;  	for (int i = 0;i < length;i++) {  //i作为终点  	    int j = i;    //j作为起点     	    while (j>=0) {     	        if (s.at(j) == s.at(i) && (i-j < 2 || p[j+1][i-1])) {     	            p[j][i] = true;                    if (i-j+1 > maxlength) {                        start = j;                        maxlength = i-j+1;                    }      	        }    		j--;     	    }   	}   	if(maxlength > 0)   		return s.substr(start,maxlength);   	return NULL;}复制代码

3.中心拓展法（Expand Around Center）

中心扩展就是把给定的字符串的每一个字母当做中心，向两边扩展，这样来找最长的子回文串。算法复杂度为 O(N^2)。 但是要考虑两种情况：

• 像aba，这样长度为奇数。

• 想abba，这样长度为偶数。

  string longestpalindrome(string s) {  	int length = s.size();  	if(length == 1)return s;  	if(length == 0)return NULL;  	int maxlength = 0;  	int start;  	for(int i = 0;i < length;i++) {     //长度为奇数  	    int j = i-1,k = i+1;  	    while(j >= 0 && k < length && s.at(j) == s.at(k)) {  	        if(k-j+1 > maxlength) {  	            maxlength = k-j+1;  	            start = j;          	}          	j--;          	k++;      	    }  	}  	for(int i=0;i < length;i++) {     //长度为偶数      	    int j = i,k = i+1;      	    while(j >= 0 && k < length && s.at(j) == s.at(k)) {      	        if(k-j+1 > maxlength) {              	    maxlength = k-j+1;              	    start = j;          	}          	j--;          	k++;      	    }  	}  	if(maxlength > 0)      	    return s.substr(start,maxlength);  	return NULL;  }复制代码

4.Manacher法

由于回文分为偶回文（比如bccb）和奇回文（比如bcacb），而在处理奇偶问题上会比较繁琐，所以这里我们使用一个技巧，具体做法是：在字符串首尾，及各字符间各插入一个字符（前提这个字符未出现在串里）。

举个例子：s="abbahopxp"，转换为 s_new="$#a#b#b#a#h#o#p#x#p#"（这里的字符$只是为了防止越界，下面代码会有说明），如此，s 里起初有一个偶回文 abba 和一个奇回文 pxp ，被转换为 #a#b#b#a# 和 #p#x#p#，长度都转换成了奇数。

定义一个辅助数组 int p[]，其中 p[i] 表示以i为中心的最长回文的半径，例如：

可以看出，p[i] - 1 正好是原字符串中最长回文串的长度。

接下来的重点就是求解 p 数组，如下图：

设置两个变量，mx 和 id。mx 代表以 id 为中心的最长回文的右边界，也就是 mx = id + p[id]。

假设我们现在求 p[i]，也就是以 i 为中心的最长回文半径，如果 i < mx，如上图，那么：

if (i < mx)      p[i] = min(p[2*id-i], mx-i);	//2*id-i为 i 关于 id 的对称点，即上图的 j 点，而 p[j] 表示以 j 为中心的最长回文半径，因此我们可以利用p[j]来加快查找。复制代码

当然光看代码还是不够清晰，还是借助图来理解比较容易。

当 mx - i > p[j] 的时候，以 s_new[j] 为中心的回文子串包含在以 s_new[id] 为中心的回文子串中，由于 i 和 j 对称，以 s_new[i] 为中心的回文子串必然包含在以 s_new[id] 为中心的回文子串中，所以必有 p[i] = p[j]，见下图。

当 p[j] >= mx - i 的时候，以 s_new[j] 为中心的回文子串不一定完全包含于以 s_new[id] 为中心的回文子串中，但是基于对称性可知，下图中两个绿框所包围的部分是相同的，也就是说以 s_new[i] 为中心的回文子串，其向右至少会扩张到mx的位置，也就是说 p[i] >= mx - i。至于 mx 之后的部分是否对称，就只能老老实实去匹配了。

对于 mx <= i 的情况，无法对 p[i] 做更多的假设，只能 p[i] = 1，然后再去匹配了。

char s_new[2000];int p[2000];int initString(string s) {    int length = s.size();    s_new[0] = '$';    s_new[1] = '#';    int j = 2;    for (int i = 0; i < length; i++) {        s_new[j++] = s[i];        s_new[j++] = '#';    }    s_new[j] = '\0';  //别忘了哦    return j;  //返回 s_new 的长度}string longestpalindrome(string s) {    int length = initString(s);  //取得新字符串长度并完成向 s_new 的转换    int maxlength = -1;  //最长回文长度    int id;    int mx = 0;    int index;    for (int i = 1; i < length; i++) {        if (i < mx)            p[i] = min(p[2*id-i], mx-i);  //需搞清楚上面那张图含义,mx 和 2*id-i 的含义        else            p[i] = 1;        while (s_new[i - p[i]] == s_new[i + p[i]])  //不需边界判断，因为左有'$',右有'\0'            p[i]++;        //我们每走一步 i，都要和 mx 比较，我们希望 mx 尽可能的远，这样才能更有机会执行 if (i < mx) 这句代码，从而提高效率        if (mx < i + p[i]) {            id = i;            mx = i + p[i];        }        if (p[i] - 1 > maxlength) {            maxlength = p[i] - 1;            index = i;        }    }    if (maxlength % 2 == 1) {        int r = maxlength / 2;        index = (index - 1) / 2;        return s.substr(index - r, maxlength);    } else {        int r = (maxlength -1) / 2;        index = (index - 2) / 2;        return s.substr(index - r, maxlength);    }}复制代码