首页 > 代码库 > LCS问题

LCS问题

LCS问题即longest common subsequence problem,中文:最长公共子序列问题

 

给你两个字符串str1和str2,它们之间可能存在公有子序列,子序列和子串的区别是:子序列不要求连续,只需要按照顺序出现就好,子串则要求连续:

例如:SIMPLE和NAIVE有共同的子序列IE,但是没有共同的子串。

      TOO SIMPLE和TOO YOUNG则有共同子串TOO

 

LCS问题就是(1)求出最长公有子序列的长度(2)求出最长公有子序列。

 

(1) 求出最长公有子序列的长度

解法考虑动态规划,用一个二维数组L [m][n]存状态, L [i][j]的含义是str1前i项和str2的前j项最长的公共子序列的长度。

写出状态转移方程:

技术分享

第一个式子比较好理解,

第二个我是这么理解的,本应该是求:

技术分享

可是很显然第三项是最小的,所以省略了。

 

(2)输出一个LCS

从状态表右下角开始往前回溯,当前字符相等,则存入结果字符串,当前字符不相等,比较状态表上方与左方的值,并移动到最大值位置,重复上述步骤,直到到达边界。反序输出结果字符串。

 

上代码:

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 int LCS(char*a,char*b){
 5     int m=strlen(a);
 6     int n=strlen(b);
 7     int L[m][n];
 8     int i,j;
 9     char res[20];
10     int k=0;
11         
12     for(i=0;i<m;i++){
13         for(j=0;j<n;j++){
14             if(i==0||j==0){
15                 L[i][j]=0;      //case 1     
16             }else{
17                 if(a[i]==b[j]){
18                     L[i][j]=L[i-1][j-1]+1;  //case 2
19                 }else{
20                     L[i][j]=L[i-1][j]>L[i][j-1]?L[i-1][j]:L[i][j-1]; // case 3
21                 }    
22             }
23             printf("%d ",L[i][j]);    
24         }
25         printf("\n");
26     }
27     
28     for(i=m-1,j=n-1;i>=0&&j>=0;){
29         if(a[i]==b[j]){
30             res[k++]=a[i];
31             i--;
32             j--;
33             
34         }else{
35             if(L[i-1][j]>L[i][j-1]){
36                 i--;
37             }else{
38                 j--;
39             }    
40         }
41     }
42 
43     printf("\nLCS:");
44     for(i=strlen(res)-1;i>=0;i--){
45         printf("%c",res[i]);
46     }
47     printf("\n");
48         
49     return L[m-1][n-1];    
50 }
51 int main(){
52     char str1[50];
53     char str2[50];
54     strcpy(str1,"SIMPLE");
55     strcpy(str2,"NAIVE");
56     int ret;
57     
58     ret=LCS(str1,str2);
59     printf("length of LCS:%d\n",ret);
60     return 0;
61 }

 

LCS问题