最长回文串算法


		给定一个字符串找出最长回文字符串范围，例如abaabac，最长回文为abaaba
1、使用暴力的算法需要O(N^3)的复杂度，需要O(N^2)的复杂度去运算字符串所用的子串，然后使用O（N）去判断是否是回文串，从而定位最长的回文子串。
[cpp]  
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的值相反，但是不影响整体的计算。
[cpp] 
#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）
[cpp]  
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;  
补充：软件开发 , C++ ,