C說話求解最長公共子字符串成績及相干的算法剖析

C說話求解最長公共子字符串成績及相干的算法剖析。本站提示廣大學習愛好者：（C說話求解最長公共子字符串成績及相干的算法剖析）文章只能為提供參考，不一定能成為您想要的結果。以下是C說話求解最長公共子字符串成績及相干的算法剖析正文

---

標題：假如字符串一的一切字符按其在字符串中的次序湧現在別的一個字符串二中，則字符串一稱之為字符串二的子串。留意，其實不請求子串（字符串一）的字符必需持續湧現在字符串二中。請編寫一個函數，輸出兩個字符串，求它們的最長公共子序列，並打印出最長公共子序列。
例如：輸出兩個字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它們的最長公共子序列，則輸入它們的長度4，並打印隨意率性一個子序列。
剖析：求最長公共子序列（Longest Common Subsequence, LCS）是一道異常經典的靜態計劃題，是以一些看重算法的公司像MicroStrategy都把它看成面試題。

完全引見靜態計劃將須要很長的篇幅，是以我不盤算在此周全評論辯論靜態計劃相干的概念，只集中對LCS直接相干內容作評論辯論。假如對靜態計劃不是很熟習，請參考相干算法書好比算法評論辯論。

斟酌最長公共子序列成績若何分化成子成績，設A=“a0，a1，…，am-1”，B=“b0，b1，…，bn-1”，並Z=“z0，z1，…，zk-1”為它們的最長公共子序列。不難證實有以下性質：

（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的最長公共子序列。

求解：
引進一個二維數組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]均已盤算出來。此時我們依據X[i] == Y[j]照樣X[i] != Y[j]，便可以盤算出c[i][j]。

成績的遞歸式寫成：

回溯輸入最長公共子序列進程：    

算法剖析：
因為每次挪用至多向上或向左（或向上向左同時）挪動一步，故最多挪用(m + n)次就會碰到i = 0或j = 0的情形，此時開端前往。前往時與遞歸挪用時偏向相反，步數雷同，故算法時光龐雜度為Θ(m + 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); 
 
  //雙指針的辦法請求靜態二維數組 
  int **c = new int*[length1+1];   //共有length1+1行 
  for(i = 0; i < length1+1; i++) 
    c[i] = new int[length2+1];   //共有length2+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++)  //釋放靜態請求的二維數組 
    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); 
  //雙指針的辦法請求靜態二維數組 
  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++)  //釋放靜態請求的二維數組 
    delete[] b[i]; 
  delete[] b; 
  system("pause"); 
  return 0; 
} 

法式的後果圖以下：

第二種辦法為：

/** 
找出兩個字符串的最長公共子序列的長度 
** 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); 
 
  //雙指針的辦法請求靜態二維數組 
  int **c = new int*[length1+1];   //共有length1+1行 
  for(i = 0; i < length1+1; i++) 
    c[i] = new int[length2+1];   //共有length2+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++)  //釋放靜態請求的二維數組 
    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的字符串，它們取自統一常數年夜小的字母表。設計一個找出三個串的最長公共子序列的O(n^3)的時光算法。
       思緒：跟下面的求2個字符串的公共子序列是一樣的思緒，只不外這裡須要靜態請求一個三維的數組，三個字符串的尾字符分歧的時刻，斟酌的情形多一些罷了。

/** 
找出三個字符串的最長公共子序列的長度 
** 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); 
 
  //請求靜態三維數組 
  int ***c = new int**[length1+1];   //共有length1+1行 
  for(i = 0; i < length1+1; i++) 
  { 
    c[i] = new int*[length2+1];   //共有length2+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++)     //釋放靜態請求的三維數組 
  { 
    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; 
} 

法式的後果圖以下：