C語言求解最長公共子字符串問題及相關的算法分析

更新時間：2016年06月04日 17:57:22 作者：hackbuteer1

最長公共子字符串問題即是求一個字符串在另一個字符串中出現(xiàn)的連續(xù)最多字符,這里我們來看一下面試中經(jīng)常出現(xiàn)的C語言求解最長公共子字符串問題及相關的算法分析

題目：如果字符串一的所有字符按其在字符串中的順序出現(xiàn)在另外一個字符串二中，則字符串一稱之為字符串二的子串。注意，并不要求子串（字符串一）的字符必須連續(xù)出現(xiàn)在字符串二中。請編寫一個函數(shù)，輸入兩個字符串，求它們的最長公共子序列，并打印出最長公共子序列。
例如：輸入兩個字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它們的最長公共子序列，則輸出它們的長度4，并打印任意一個子序列。
分析：求最長公共子序列（Longest Common Subsequence, LCS）是一道非常經(jīng)典的動態(tài)規(guī)劃題，因此一些重視算法的公司像MicroStrategy都把它當作面試題。

完整介紹動態(tài)規(guī)劃將需要很長的篇幅，因此我不打算在此全面討論動態(tài)規(guī)劃相關的概念，只集中對LCS直接相關內(nèi)容作討論。如果對動態(tài)規(guī)劃不是很熟悉，請參考相關算法書比如算法討論。

考慮最長公共子序列問題如何分解成子問題，設A=“a0，a1，…，am-1”，B=“b0，b1，…，bn-1”，并Z=“z0，z1，…，zk-1”為它們的最長公共子序列。不難證明有以下性質(zhì)：

（1）如果am-1==bn-1，則zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一個最長公共子序列；

（2）如果am-1!=bn-1，則若zk-1!=am-1時，蘊涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一個最長公共子序列；

（3）如果am-1!=bn-1，則若zk-1!=bn-1時，蘊涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個最長公共子序列。

這樣，在找A和B的公共子序列時，如果有am-1==bn-1，則進一步解決一個子問題，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一個最長公共子序列；如果am-1!=bn-1，則要解決兩個子問題，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一個最長公共子序列和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個最長公共子序列，再取兩者中較長者作為A和B的最長公共子序列。

求解：
引進一個二維數(shù)組c[][]，用c[i][j]記錄X[i]與Y[j] 的LCS 的長度，b[i][j]記錄c[i][j]是通過哪一個子問題的值求得的，以決定輸出最長公共字串時搜索的方向。
我們是自底向上進行遞推計算，那么在計算c[i,j]之前，c[i-1][j-1]，c[i-1][j]與c[i][j-1]均已計算出來。此時我們根據(jù)X[i] == Y[j]還是X[i] != Y[j]，就可以計算出c[i][j]。

問題的遞歸式寫成：

201664173807574.gif (673×287)

回溯輸出最長公共子序列過程：

201664173831586.gif (674×501)

算法分析：
由于每次調(diào)用至少向上或向左（或向上向左同時）移動一步，故最多調(diào)用(m + n)次就會遇到i = 0或j = 0的情況，此時開始返回。返回時與遞歸調(diào)用時方向相反，步數(shù)相同，故算法時間復雜度為Θ(m + n)。

完整的實現(xiàn)代碼如下：

/** 
找出兩個字符串的最長公共子序列的長度 
** author :liuzhiwei  
** data  :2011-08-15 
**/  
#include "stdio.h" 
#include "string.h" 
#include "stdlib.h" 
int LCSLength(char* str1, char* str2, int **b) 
{ 
  int i,j,length1,length2,len; 
  length1 = strlen(str1); 
  length2 = strlen(str2); 
 
  //雙指針的方法申請動態(tài)二維數(shù)組 
  int **c = new int*[length1+1];   //共有l(wèi)ength1+1行 
  for(i = 0; i < length1+1; i++) 
    c[i] = new int[length2+1];   //共有l(wèi)ength2+1列 
 
  for(i = 0; i < length1+1; i++) 
    c[i][0]=0;    //第0列都初始化為0 
  for(j = 0; j < length2+1; j++) 
    c[0][j]=0;    //第0行都初始化為0 
 
  for(i = 1; i < length1+1; i++) 
  { 
    for(j = 1; j < length2+1; j++) 
    { 
      if(str1[i-1]==str2[j-1])  //由于c[][]的0行0列沒有使用，c[][]的第i行元素對應str1的第i-1個元素 
      { 
        c[i][j]=c[i-1][j-1]+1; 
        b[i][j]=0;     //輸出公共子串時的搜索方向 
      } 
      else if(c[i-1][j]>c[i][j-1]) 
      { 
        c[i][j]=c[i-1][j]; 
        b[i][j]=1; 
      } 
      else 
      { 
        c[i][j]=c[i][j-1]; 
        b[i][j]=-1; 
      } 
    } 
  } 
  /* 
  for(i= 0; i < length1+1; i++) 
  { 
  for(j = 0; j < length2+1; j++) 
  printf("%d ",c[i][j]); 
  printf("\n"); 
  } 
  */ 
  len=c[length1][length2]; 
  for(i = 0; i < length1+1; i++)  //釋放動態(tài)申請的二維數(shù)組 
    delete[] c[i]; 
  delete[] c; 
  return len; 
} 
void PrintLCS(int **b, char *str1, int i, int j) 
{ 
  if(i==0 || j==0) 
    return ; 
  if(b[i][j]==0) 
  { 
    PrintLCS(b, str1, i-1, j-1);  //從后面開始遞歸，所以要先遞歸到子串的前面，然后從前往后開始輸出子串 
    printf("%c",str1[i-1]);    //c[][]的第i行元素對應str1的第i-1個元素 
  } 
  else if(b[i][j]==1) 
    PrintLCS(b, str1, i-1, j); 
  else 
    PrintLCS(b, str1, i, j-1); 
} 
 
int main(void) 
{ 
  char str1[100],str2[100]; 
  int i,length1,length2,len; 
  printf("請輸入第一個字符串："); 
  gets(str1); 
  printf("請輸入第二個字符串："); 
  gets(str2); 
  length1 = strlen(str1); 
  length2 = strlen(str2); 
  //雙指針的方法申請動態(tài)二維數(shù)組 
  int **b = new int*[length1+1]; 
  for(i= 0; i < length1+1; i++) 
    b[i] = new int[length2+1]; 
  len=LCSLength(str1,str2,b); 
  printf("最長公共子序列的長度為：%d\n",len); 
  printf("最長公共子序列為："); 
  PrintLCS(b,str1,length1,length2); 
  printf("\n"); 
  for(i = 0; i < length1+1; i++)  //釋放動態(tài)申請的二維數(shù)組 
    delete[] b[i]; 
  delete[] b; 
  system("pause"); 
  return 0; 
}

程序的效果圖如下：

201664174047130.gif (674×285)

第二種方法為：

/** 
找出兩個字符串的最長公共子序列的長度 
** author :liuzhiwei  
** data  :2011-08-15 
**/  
#include "stdio.h" 
#include "string.h" 
#include "stdlib.h" 
int LCSLength(char* str1, char* str2)  //求得兩個字符串的最大公共子串長度并輸出公共子串 
{ 
  int i,j,length1,length2; 
  length1 = strlen(str1); 
  length2 = strlen(str2); 
 
  //雙指針的方法申請動態(tài)二維數(shù)組 
  int **c = new int*[length1+1];   //共有l(wèi)ength1+1行 
  for(i = 0; i < length1+1; i++) 
    c[i] = new int[length2+1];   //共有l(wèi)ength2+1列 
 
  for(i = 0; i < length1+1; i++) 
    c[i][0]=0;    //第0列都初始化為0 
  for(j = 0; j < length2+1; j++) 
    c[0][j]=0;    //第0行都初始化為0 
 
  for(i = 1; i < length1+1; i++) 
  { 
    for(j = 1; j < length2+1; j++) 
    { 
      if(str1[i-1]==str2[j-1])  //由于c[][]的0行0列沒有使用，c[][]的第i行元素對應str1的第i-1個元素 
        c[i][j]=c[i-1][j-1]+1; 
      else if(c[i-1][j]>c[i][j-1]) 
        c[i][j]=c[i-1][j]; 
      else 
        c[i][j]=c[i][j-1]; 
    } 
  } 
 
  //輸出公共子串 
  char s[100]; 
  int len,k; 
  len=k=c[length1][length2]; 
  s[k--]='\0'; 
  i=length1,j=length2; 
  while(i>0 && j>0) 
  { 
    if(str1[i-1]==str2[j-1]) 
    { 
      s[k--]=str1[i-1]; 
      i--; 
      j--; 
    } 
    else if(c[i-1][j]<c[i][j-1]) 
      j--; 
    else 
      i--; 
  } 
  printf("最長公共子串為："); 
  puts(s); 
 
  for(i = 0; i < length1+1; i++)  //釋放動態(tài)申請的二維數(shù)組 
    delete[] c[i]; 
  delete[] c; 
  return len; 
} 
 
int main(void) 
{ 
  char str1[100],str2[100]; 
  int length1,length2,len; 
 
  printf("請輸入第一個字符串："); 
  gets(str1); 
  printf("請輸入第二個字符串："); 
  gets(str2); 
  length1 = strlen(str1); 
  length2 = strlen(str2); 
  len=LCSLength(str1,str2); 
  printf("最長公共子串的長度為：%d\n",len); 
  system("pause"); 
  return 0; 
}

問題拓展：設A、B、C是三個長為n的字符串，它們?nèi)∽酝怀?shù)大小的字母表。設計一個找出三個串的最長公共子序列的O(n^3)的時間算法。
思路：跟上面的求2個字符串的公共子序列是一樣的思路，只不過這里需要動態(tài)申請一個三維的數(shù)組，三個字符串的尾字符不同的時候，考慮的情況多一些而已。

/** 
找出三個字符串的最長公共子序列的長度 
** author :liuzhiwei  
** data  :2011-08-15 
**/  
#include "stdio.h" 
#include "string.h" 
#include "stdlib.h" 
int max1(int m,int n) 
{ 
  if(m>n) 
    return m; 
  else 
    return n; 
} 
int max2(int x,int y,int z,int k,int m,int n) 
{ 
  int max=-1; 
  if(x>max) 
    max=x; 
  if(y>max) 
    max=y; 
  if(z>max) 
    max=z; 
  if(k>max) 
    max=k; 
  if(m>max) 
    max=m; 
  if(n>max) 
    max=n; 
  return max; 
} 
int LCSLength(char* str1, char* str2, char* str3)  //求得三個字符串的最大公共子序列長度并輸出公共子序列 
{ 
  int i,j,k,length1,length2,length3,len; 
  length1 = strlen(str1); 
  length2 = strlen(str2); 
  length3 = strlen(str3); 
 
  //申請動態(tài)三維數(shù)組 
  int ***c = new int**[length1+1];   //共有l(wèi)ength1+1行 
  for(i = 0; i < length1+1; i++) 
  { 
    c[i] = new int*[length2+1];   //共有l(wèi)ength2+1列 
    for(j = 0; j<length2+1; j++) 
      c[i][j] = new int[length3+1]; 
  } 
 
  for(i = 0; i < length1+1; i++) 
  { 
    for(j = 0; j < length2+1; j++) 
      c[i][j][0]=0; 
  } 
  for(i = 0; i < length2+1; i++) 
  { 
    for(j = 0; j < length3+1; j++) 
      c[0][i][j]=0; 
  } 
  for(i = 0; i < length1+1; i++) 
  { 
    for(j = 0; j < length3+1; j++) 
      c[i][0][j]=0;   
  } 
 
  for(i = 1; i < length1+1; i++) 
  { 
    for(j = 1; j < length2+1; j++) 
    { 
      for(k = 1; k < length3+1; k++) 
      { 
        if(str1[i-1]==str2[j-1] && str2[j-1]==str3[k-1]) 
          c[i][j][k]=c[i-1][j-1][k-1]+1; 
        else if(str1[i-1]==str2[j-1] && str1[i-1]!=str3[k-1]) 
          c[i][j][k]=max1(c[i][j][k-1],c[i-1][j-1][k]); 
        else if(str1[i-1]==str3[k-1] && str1[i-1]!=str2[j-1]) 
          c[i][j][k]=max1(c[i][j-1][k],c[i-1][j][k-1]); 
        else if(str2[j-1]==str3[k-1] && str1[i-1]!=str2[j-1]) 
          c[i][j][k]=max1(c[i-1][j][k],c[i][j-1][k-1]); 
        else 
        { 
          c[i][j][k]=max2(c[i-1][j][k],c[i][j-1][k],c[i][j][k-1],c[i-1][j-1][k],c[i-1][j][k-1],c[i][j-1][k-1]); 
        } 
      } 
    } 
  } 
  len=c[length1][length2][length3]; 
  for(i = 1; i < length1+1; i++)     //釋放動態(tài)申請的三維數(shù)組 
  { 
    for(j = 1; j < length2+1; j++) 
      delete[] c[i][j]; 
    delete[] c[i]; 
  } 
  delete[] c; 
  return len; 
} 
 
int main(void) 
{ 
  char str1[100],str2[100],str3[100]; 
  int len; 
 
  printf("請輸入第一個字符串："); 
  gets(str1); 
  printf("請輸入第二個字符串："); 
  gets(str2); 
  printf("請輸入第三個字符串："); 
  gets(str3); 
  len=LCSLength(str1,str2,str3); 
  printf("最長公共子序列的長度為：%d\n",len); 
  system("pause"); 
  return 0; 
}

程序的效果圖如下：

201664175534056.gif (673×287)