先帖个代码
// project1.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include<string.h> #define LENGTH 1000 //最大回文串，动态规划法:对暴力搜索的改进 //暴力搜索O(N^2)个子串，每次O(N)，总开销O(N^3) //通过动态规划法复杂度可以降到O(N^2) int LPS_dp(char *str){ int len=strlen(str); bool dp[LENGTH][LENGTH];//dp[i][j]记录子串[i..j]是否回文 int maxlen=0,beg_pos=0; for(int i=0;i<len;i++){ dp[i][i]=1;//单字符回文 if(i>0 && str[i-1]==str[i]) dp[i-1][i]=1;//双字符回文.dp[a][b]表示str[a..b]的子串是否是回文串，如果是，标记1 } for(int length=2;length<len;length++){//回文串长 for(int begin=0;begin<len-length;begin++){//起始位置 int end=begin+length; if(str[begin]==str[end] && dp[begin+1][end-1]==1){ dp[begin][end]=1; if(end-begin+1>maxlen){ maxlen=end-begin+1; beg_pos=begin; } } } } return maxlen; } //O(N^2)复杂度 int LPS_two(char *str){ int LPS_rb[LENGTH];//i为中心的回文子串右边界下标right border char new_str[LENGTH];//保存对str处理后的数组 memset(new_str,0,sizeof(char)*LENGTH); int maxlen=0; new_str[0]='$'; new_str[1]='#'; //为什么要对原数组进行处理呢？ //例如，原本aba变成$a#b#a#，这样不管是单字符回文还是双字符回文，都可以用new_str[i-k] == new_str[i+k]进行比较 for(char *p=str,i=2;*p;p++){//处理数组 new_str[i]=*p; new_str[i+1]='#'; i+=2; } int len=strlen(new_str); for(int i=1;i<len;i++){//计算LPS_rb数组 LPS_rb[i]=1;//初始化 while(new_str[i-LPS_rb[i]]==new_str[i+LPS_rb[i]]) LPS_rb[i]++; if(LPS_rb[i]-1>maxlen) maxlen=LPS_rb[i]-1; } return maxlen; } //对LPS_two的优化，复杂度降到O(N) int LPS_two_opt(char *str){ int LPS_rb[LENGTH];//i为中心的回文子串右边界下标right border char new_str[LENGTH];//保存对str处理后的数组 memset(new_str,0,sizeof(char)*LENGTH);
//增加了这几个字段 //maxlen为LPS的长度，max_center中心位置，max_rb为右边界 int maxlen=0,max_center=0,max_rb=0; new_str[0]='$'; new_str[1]='#'; //为什么要对原数组进行处理呢？ //例如，原本aba变成$a#b#a# for(char *p=str,i=2;*p;p++){//处理数组 new_str[i]=*p; new_str[i+1]='#'; i+=2; } int len=strlen(new_str); for(int i=1;i<len;i++){//计算LPS_rb数组
//本算法的核心在此。这个if语句将复杂度降到O(N) if(max_rb>i) //max_rb为当前最大串的右边界 //如果最大串的右边界在i之后
//LPS_rb[i]表示以i为中心的回文串的右边界
//如果max_rb>i,则说明在以max_center为中心对称的左侧也有个字符即str[2*max_center -i] = str[i] //于是可以利用已计算好的str[2*max_center-i]的LPS_rb[2*max_center-i]来计算LPS_rb[i],于是LPS_rb[i]至少大于等于 min(LPS_rb[2*max_center-i],(max_rb-i)) //2*max_center-i为i关于max_center的对称点 LPS_rb[i] = (LPS_rb[2*max_center-i]<(max_rb-i)) ? LPS_rb[2*max_center-i]:(max_rb-i); else LPS_rb[i]=1; //从min(LPS_rb[2*max_center-i],(max_rb-i))开始增加，这样如此便节省了一些次的循环，因此会降低算法复杂度 while(new_str[i-LPS_rb[i]]==new_str[i+LPS_rb[i]]) LPS_rb[i]++; if(LPS_rb[i]-1>maxlen){ maxlen=LPS_rb[i]-1; max_center=i; max_rb=i+maxlen; } } return maxlen; } int _tmain(int argc, _TCHAR* argv[]) { char str1[LENGTH]="abbaeaabccbaeeaee"; char str2[LENGTH]="aaaaaaaaa"; char str3[LENGTH]="abababababab"; printf("LPS:%d ",LPS_dp(str1));printf("LPS:%d ",LPS_dp(str2));printf("LPS:%d ",LPS_dp(str3)); printf("LPS:%d ",LPS_two(str1));printf("LPS:%d ",LPS_two(str2));printf("LPS:%d ",LPS_two(str3)); printf("LPS:%d ",LPS_two_opt(str1));printf("LPS:%d ",LPS_two_opt(str2));printf("LPS:%d ",LPS_two_opt(str3)); return 0; }