给定一个字符串找出最长回文字符串范围，例如abaabac，最长回文为abaaba
1、使用暴力的算法需要O(N^3)的复杂度，需要O(N^2)的复杂度去运算字符串所用的子串，然后使用O（N）去判断是否是回文串，从而定位最长的回文子串。
int lps_bl(char str[], int len){
if(str == NULL || len <= 0){
return 0;
}
int i, j;
int start, end, max_lps;
for(i = 0; i < len; i++){
for(j = 1; j < len; j++){
start = 0;
end = len - 1;
while(start <= end && str[start] == str[end]){
start++;
end--;
}
if(start >= end){
if(j > max_lps){
max_lps = j;
}
}
}
}
printf("lps_bl:%d\n", max_lps);
return max_lps;
}
可以看到这种算法很容易理解，只是O(N^3)的复杂度相对比较高。
2、使用动态规划的思想进行求解，思路是利用子串从短到长进行逐步的动态规划求解，可以理解为从中心向两边扩散，如果一个字符串的子串是回文串，那么就可以存储这个状态，然后从短向长蔓延进行计算：
当i == j 时 肯定是长度为1 的回文串，dp[i][j] = 1
当dp[i][j] == 1 时如果S[i-1] == S[j+1]， dp[i][j] == 1，（如果子串是回文串，并且首尾相同，那么当前的子串也是回文串）
当i+1 == j 时，S[i] == S[j]， 那么dp[i][j] == 1，这个状态值在计算时会有些特殊，因为 j = i +1，那么i-1和j+1会与i和j的值相反，但是不影响整体的计算。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int lps_dp(char str[], int len)
{
if(str == NULL || len <= 0){
return 0;
}
int dp[100][100] = {0};
int i,j, m;
for(i = 0; i < 100; i++){
dp[i][i] = 1;
}
int start = 0;
int end = 0;
int max_lps = 0;
char buf[100] = {0};
//printf("len:%d\n", len);
for(m = 1; m < len; m++){
printf("m=%d\n", m);
for(i = 0; i < len - m; i++){
j = i + m;
memcpy(buf, str + i, j-i + 1);
buf[j-i + 1] = '\0';
//printf("%d\t%d\t%s\n", i, j,buf);
//printf("dp[%d][%d]=%d\n", (i+1), (j-1), dp[i+1][j-1]);
if(i + 1 == j && str[i] == str[j]){
dp[i][j] = 1;
int tmp = j - i + 1;
if(tmp > max_lps){
start = i;
end = j;
max_lps = tmp;
}
}else if(dp[i+1][j-1] == 1 && str[i] == str[j]){
dp[i][j] = 1;
int tmp = j - i + 1;
if(tmp > max_lps){
start = i;
end = j;
max_lps = tmp;
}
}
}
}
//memcpy(buf, str+start, max_lps);
//buf[max_lps] = '\0';
//printf("max_len:%d\tlps:%s\n", max_lps, buf);
return max_lps;
}
3、受以上动态规划算法的启发，可以考虑选取中间点，然后逐步向两边蔓延的策略进行回文串的判断，这种方法相对于动态规划的算法更容易理解，而且空间复杂度会由O(N^2)变为O（1）
int lps_ext(char str[], int len){
if(str == NULL || len <= 0){
return 0;
}
int i;
int max_lps = 1;
int start = 0;
char buf[100] = {0};
for(i = 1; i < len; i++){
int low = i - 1;
int high = i;
//数组的元素是偶数个
while(low >= 0 && high < len && str[low] == str[high]){
if(high - low + 1> max_lps){
start = low;
max_lps = high - low + 1;
}
low--;
high++;
}
//数组的元素是奇数个
low = i - 1;
high = i + 1;
while(low >= 0 && high < len && str[low] == str[high]){
if(high - low + 1 > max_lps){
start = low;
max_lps = high - low +1;
}
low--;
high++;
}
}
memcpy(buf, str + start, max_lps);
printf("%d\tlps_ext:%s\n",max_lps, buf);
return max_lps;
}
下面介绍一种O（N）的算法：Manacher，
这个算法开始理解起来比较复杂，但确实有一定的技巧性，第一个技巧是将可能的回文串，无论是奇数个字符还是偶数个字符全部变为奇数，这样有利于利用对称性特征进行计算，变换方式如下：
在每个字符的两边都插入一个特殊的符号。比如 abba 变成 #a#b#b#a#， aba变成 #a#b#a#。 为了进一步减少编码的复杂度，可以在字符串的开始加入另一个特殊字符，这样就不用特殊处理越界问题，比如$#a#b#a#。
下面以字符串12212321为例，经过上一步，变成了 S[] = "$#1#2#2#1#2#3#2#1#";
算法引入两个变量id和mx，id表示最长回文子串的中心位置，mx表示最长回文字串的边界位置，即：mx=id+P[id]。
在这里有一个非常有用而且神奇的结论：如果mx > i，那么P[i] >= MIN(P[2 * id - i], mx - i) 分开理解就是：
如果mx - i > P[j], 则P[i]=P[j]
否则，P[i] = mx - i.
这两个该如何理解呢？具体的解释请看下面的两个图。
当 mx - i > P[j] 的时候，以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中，由于 i 和 j 对称，以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中，所以必有 P[i] = P[j]，见下图。
当 P[j] >= mx - i 的时候，以S[j]为中心的回文子串不一定完全包含于以S[id]为中心的回文子串中，但是基于对称性可知，下图中两个绿框所包围的部分是相同的，也就是 说以S[i]为中心的回文子串，其向右至少会扩张到mx的位置，也就是说 P[i] >= mx - i。至于mx之后的部分是否对称，就只能老老实实去匹配了。
对于 mx <= i 的情况，无法对 P[i]做更多的假设，只能P[i] = 1，然后再去匹配了。
下面的算法没有做字符串变换和恢复，大家有兴趣可以自己实现。
以上参考这两个博客
Manacher's ALGORITHM: O(n)时间求字符串的最长回文子串
int min(int arg1, int arg2){
return arg1 > arg2 ? arg1: arg2;
}
int lps_liner(char str[], int len){
if(str == NULL || len <= 0){
return 0;
}
int lps[100] = {0};
int i;
int mx = 0, id = 0;
for(i = 1; str[i] != '\0'; i++){
lps[i] = mx > i ? min(lps[2*id -i], mx -i) : 1;
while(str[i + lps[i]] == str[i - lps[i]]) lps[i]++;
if(i + lps[i] > mx){
mx = i + lps[i];
id = i;
}
}
int max = 0;
for(i = 0; i < len; i++){
if(lps[i] > max){
max = lps[i];
}
}
printf("lps_liner:%d\n", max);
}
int main(int argc, char *argv[]){
char *str = argv[1];
int len = strlen(str);
lps_dp(str, len);
lps_ext(str, len);
lps_liner(str, len);
}