最长回文字符串常用求法

 最长回文字符串常用求法一般有以下几种：

1 暴力求解

先给出每个字串s[i...j]，i=0...len,j=i,...len，其时间复杂度O（N^2），再针对每个字串判断是否是回文需要时间O（N），故该算法时间复杂度O（N^3），空间复杂度O（1）。

#define max 100+10
char buf[max*2];
char tmp[max*2];
void get_longest_str(){
printf("请输入字符串\n");
fgets(buf,max,stdin);//fgets输入，遇见换行才停
int len=strlen(buf);
int i,j=0;
int p[max*2]={0};//pi存储的是tmpi在Buf位置
for(i=0;i<len;i++)
    if(isalpha(buf[i])){tmp[j]=toupper(buf[i]);p[j]=i;j++;}//tmp存的都是大写字母
int s_len=j;
int max_len=0;
int ii,jj;
printf("%s\n",tmp);
for(i=0;i<s_len;i++)//  for each element in string
    for(j=i;j<s_len;j++)//start at i
      {//判断s[i..j]是一个回文串
	  bool f=1;
	  for(int k=i;k<=j;k++)
	      if(tmp[k]!=tmp[i+j-k])f=0;
	  if(f&&j-i+1>max_len){max_len=j-i+1;ii=i;jj=j;}
      }
printf("最大回文长度：%d\n",max_len);
for(i=p[ii];i<=p[jj];i++)
    printf("%c",buf[i]);
printf("\n");
}
           

2 动态规划

动态规划是暴力解法的改进，引入二维数组p[i][j]，p[i][j]=1表示字串s[i]到s[j]是回文故由动态规划思想:

初始：

p[i][j]=1, if j=i

p[i][j]=1,if j=i+1&&s[i]=s[i+1]

动态：

p[i][j]=1,if s[i]=s[j]&&p[i+1][j-1]=1

故不同于暴力求解，针对每个字串，只需判断p[i][j]=1即可，时间复杂度O（1），总体而言，时间复杂度O（N^2），空间复杂度O(N^2)

void get_longest_str_update(){
printf("请输入字符串:\n");
fgets(buf,max,stdin);
int len=strlen(buf);
int i,j=0;
int p[max*2]={0};
for(i=0;i<len;i++)
    if(isalpha(buf[i])){tmp[j]=toupper(buf[i]);p[j]=i;j++;}
int s_len=j;
int max_len=0;int ii,jj;
//动态规划
bool table[max][max]={0};
for(i=0;i<s_len;i++)
    table[i][i]=1;
for(i=0;i<s_len-1;i++)
    if(tmp[i]==tmp[i+1]){table[i][i+1]=1;max_len=2;ii=i;jj=i+1;}
//以上两个for为初始化
for(int l=3;l<=s_len;l++)//字串长度
   for(i=0;i<=s_len-l;i++)//字串起始位置
   {
       j=i+l-1;//l=j-i+1
       if(table[i+1][j-1]==1&&tmp[i]==tmp[j])
       {table[i][j]=1;max_len=l;ii=i;jj=j;
       }
   }
printf("最大回文长度：%d\n",max_len);
for(i=p[ii];i<=p[jj];i++)
    printf("%c",buf[i]);
printf("\n");
}
           

3 中心扩展

中心扩展就是把给定的字符串的每一个字母当做中心，向两边扩展，这样来找最长的子回文串。算法复杂度为O(N^2)。唯一需要注意的是字串长度为奇数和偶数分开讨论。

void get_longest_str_expand(){
printf("请输入字符串:\n");
fgets(buf,max,stdin);
int len=strlen(buf);
int i,j=0,k;
int p[max*2]={0};
for(i=0;i<len;i++)
    if(isalpha(buf[i])){tmp[j]=toupper(buf[i]);p[j]=i;j++;}
int s_len=j;
int max_len=0;int ii,jj;
for(i=0;i<s_len;i++)
{j=i-1;k=i+1;
    while(j>=0&&k<s_len&&tmp[j]==tmp[k]){
	if(k-j+1>max_len){
	max_len=k-j+1;ii=j;jj=k;}
	j--;k++;//以i为中心向两边散开
                                        }
}//长度为奇数
for(i=0;i<s_len;i++)
{j=i;k=i+1;
    while(j>=0&&k<s_len&&tmp[j]==tmp[k]){
	if(k-j+1>max_len){
	    max_len=k-j+1;ii=j;jj=k;
	                  }
	j--;k++;
                                         }
}
printf("最大回文长度：%d\n",max_len);
for(i=p[ii];i<=p[jj];i++)
    printf("%c",buf[i]);
printf("\n");

}