C語言求解最長(zhǎng)公共子字符串問題及相關(guān)的算法分析

2020-01-26 14:34:08

字體：大中小

供稿：網(wǎng)友

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

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

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

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

（2）如果am-1!=bn-1，則若zk-1!=am-1時(shí)，蘊(yùn)涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一個(gè)最長(zhǎng)公共子序列；

（3）如果am-1!=bn-1，則若zk-1!=bn-1時(shí)，蘊(yùn)涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個(gè)最長(zhǎng)公共子序列。

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

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

問題的遞歸式寫成：

201664173807574.gif (673×287)

回溯輸出最長(zhǎng)公共子序列過程：

201664173831586.gif (674×501)

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

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

/** 找出兩個(gè)字符串的最長(zhǎng)公共子序列的長(zhǎng)度 ** 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);    //雙指針的方法申請(qǐng)動(dòng)態(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行元素對(duì)應(yīng)str1的第i-1個(gè)元素       {         c[i][j]=c[i-1][j-1]+1;         b[i][j]=0;     //輸出公共子串時(shí)的搜索方向       }       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++)  //釋放動(dòng)態(tài)申請(qǐng)的二維數(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行元素對(duì)應(yīng)str1的第i-1個(gè)元素   }   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("請(qǐng)輸入第一個(gè)字符串：");   gets(str1);   printf("請(qǐng)輸入第二個(gè)字符串：");   gets(str2);   length1 = strlen(str1);   length2 = strlen(str2);   //雙指針的方法申請(qǐng)動(dòng)態(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("最長(zhǎng)公共子序列的長(zhǎng)度為：%d/n",len);   printf("最長(zhǎng)公共子序列為：");   PrintLCS(b,str1,length1,length2);   printf("/n");   for(i = 0; i < length1+1; i++)  //釋放動(dòng)態(tài)申請(qǐng)的二維數(shù)組     delete[] b[i];   delete[] b;   system("pause");   return 0; }

程序的效果圖如下：

201664174047130.gif (674×285)

第二種方法為：

/** 找出兩個(gè)字符串的最長(zhǎng)公共子序列的長(zhǎng)度 ** author :liuzhiwei  ** data  :2011-08-15 **/  #include "stdio.h" #include "string.h" #include "stdlib.h" int LCSLength(char* str1, char* str2)  //求得兩個(gè)字符串的最大公共子串長(zhǎng)度并輸出公共子串 {   int i,j,length1,length2;   length1 = strlen(str1);   length2 = strlen(str2);    //雙指針的方法申請(qǐng)動(dòng)態(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行元素對(duì)應(yīng)str1的第i-1個(gè)元素         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("最長(zhǎng)公共子串為：");   puts(s);    for(i = 0; i < length1+1; i++)  //釋放動(dòng)態(tài)申請(qǐng)的二維數(shù)組     delete[] c[i];   delete[] c;   return len; }  int main(void) {   char str1[100],str2[100];   int length1,length2,len;    printf("請(qǐng)輸入第一個(gè)字符串：");   gets(str1);   printf("請(qǐng)輸入第二個(gè)字符串：");   gets(str2);   length1 = strlen(str1);   length2 = strlen(str2);   len=LCSLength(str1,str2);   printf("最長(zhǎng)公共子串的長(zhǎng)度為：%d/n",len);   system("pause");   return 0; }

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

/** 找出三個(gè)字符串的最長(zhǎng)公共子序列的長(zhǎng)度 ** 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)  //求得三個(gè)字符串的最大公共子序列長(zhǎng)度并輸出公共子序列 {   int i,j,k,length1,length2,length3,len;   length1 = strlen(str1);   length2 = strlen(str2);   length3 = strlen(str3);    //申請(qǐng)動(dòng)態(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++)     //釋放動(dòng)態(tài)申請(qǐng)的三維數(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("請(qǐng)輸入第一個(gè)字符串：");   gets(str1);   printf("請(qǐng)輸入第二個(gè)字符串：");   gets(str2);   printf("請(qǐng)輸入第三個(gè)字符串：");   gets(str3);   len=LCSLength(str1,str2,str3);   printf("最長(zhǎng)公共子序列的長(zhǎng)度為：%d/n",len);   system("pause");   return 0; }

程序的效果圖如下：

201664175534056.gif (673×287)