最長回文字元串常用求法

 最長回文字元串常用求法一般有以下幾種：

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");

}