您的位置: 首页  >  文章  >  最长公共子序列问题（不要求连续）

最长公共子序列问题（不要求连续）

分类: 文章 • 2024-09-02 09:52:04
下面这篇文章介绍一下在算法设计中动态规划的最长公共子序列的问题。

最长公共子序列问题所谓，也即是分别给出长度为n和m的字符串A，B，然后找出其中最长公共子序列的最优值和最优解。

所谓最优值，也就是求出这个最长公共子序列的长度；而最优解，就是要求出这个最长最长公共子序列是什么的问题。给个不太恰当的例子：我们中学数学中经常会遇到求函数最值的问题，比如说求出函数 f（x） 的最大值，那么这个最大值就是最优值了；而最优解是什么呢？就是当f（x）取到最大值的时候的 x 值了。


解决的方法其实最简单的就是使用蛮力的方法，列举某一个字符串中的所有子序列，也就是求出这个字符串子序列的幂集；然后分别与另一字符串进行比较。那么由于幂集是 2 的 n 次方。所以其时间复杂度也就是 2 的 n 次方。

那么采用动态规划，可以通过寻求一个求最长公共子序列长度（下面简称LCS）的递推公式。

假设字符串  A = a1  a2  a3  a4.....ai                    B = b1  b2  b3  b4......bj

L[ i , j ]表示字符串A 和 B的最长公共子序列的长度。

那么：

最长公共子序列问题（不要求连续）

稍作解释：①假如字符串A B中，有一个是长度为0；那么LCS = 0；

②假如，两个字符串的最后一个字符相同，那么其长度等于，A,B前面字符的匹配结果 +1

③假如，两个字符串的最后一个字符不相同，那么其长度等于，A减去最后一个字符和B进行匹配的结果，B减去最后一个字符和A进行匹配的结果，二者的最大值。


所以对于这个问题的求解，我们可以用一个二维表来进行计算求解，利用上面的公式逐行的填表。二维表的最后一个元素即是问题的最优值。

下面给出伪代码的实现：

最长公共子序列问题（不要求连续）

[cpp] view plain copy
  1. #include<stdio.h>  
  2. #include<string.h>  
  3.   
  4.   
  5. int getMax(int a,int b)  
  6. {  
  7.     return a>b?a:b;  
  8. }  
  9. char res[100];  
  10. //注意数组和字符串下标都是从0开始的  
  11. int LCS(char strA[],char strB[])  
  12. {  
  13.     int lenA = strlen(strA);  
  14.     int lenB = strlen(strB);  
  15.     printf("%d,%d",lenA,lenB);  
  16.     int n = lenA+1;  
  17.     int m = lenB+1;  
  18.   
  19.     //创建一个二维数组 n 行 m 列  
  20.     int result[n][m];  
  21.     int i,j;  
  22.     for(i = 0; i < n; i++) result[i][0] = 0; //将第一列全部置零  
  23.     for(j = 0; j < m; j++) result[0][j] = 0; //将第一行全部置零  
  24.     int nn = 0;  
  25.     for(i = 1; i< n; i++)  
  26.         for(j = 1; j < m; j++) //逐行填充表格  
  27.         {  
  28.             //如果两个字符相等，则result[i][j]等于表中左上角元素值+1  
  29.             if(strA[i-1] == strB[j-1]) result[i][j] = result[i-1][j-1]+1;  
  30.             //如果两个字符不相等，则result[i][j]等于表中左边或者是上边元素值的最大者  
  31.             //result[i][j-1]表示左边元素;result[j][i-1]表示s上边元素  
  32.             else result[i][j] = getMax(result[i][j-1],result[i-1][j]);  
  33.         }  
  34.   
  35.     int returnNum = result[n-1][m-1];//最后返回的结果：最长公共子序列长度  
  36.   
  37.     return returnNum;  
  38. }  
  39.   
  40. int main()  
  41. {  
  42.     char strA[100],strB[100];  
  43.     printf("请输入第一个字符串：");  
  44.     scanf("%s",strA);  
  45.   
  46.     printf("请输入第二个字符串：");  
  47.     scanf("%s",strB);  
  48.   
  49.     int num = LCS(strA,strB);  
  50.   
  51.     printf("最长公共子序列的长度是%d",num);  
  52. }  

http://blog.****.net/hackbuteer1/article/details/6686925

这个博客里面的第二种方法打印出公共自序列

相关推荐