首页 > 代码库 > LCS (Longest Common Subsequence)

LCS (Longest Common Subsequence)

2024-07-15 16:02:24   224人阅读

LCS是两个序列相似性的一种度量方法；

若序列s1：2,5,7,9,3,1,2

         s2：3,5,3,2,8

则LCS为：5,3,2

思路可参考：http://www.csie.ntnu.edu.tw/~u91029/LongestCommonSubsequence.html

具体代码实现为：

 1 #include<iostream> 2 using namespace std; 3  4 int s1[7+1]={0,2,5,7,9,3,1,2}; 5 int s2[7+1]={0,3,5,3,2,8}; 6 const int s1_length=8; 7 const int s2_length=6; 8 const int LEFT=1; 9 const int UP=2;10 const int UP_LEFT=3;11 const int LEFTORUP=4;12 13 int arr[7+1][5+1]={0};14 int pre[7+1][5+1]={0};15 16 void LCS();17 void print_LCS(int i,int j);18 19 int main()20 {21     cout<<"the LCS of the sequence is:";22     LCS();23     return 0;24 }25 26 void LCS()27 {28     for(int i=0;i<s2_length;++i)29         arr[0][i]=0;30     for(int i=0;i<s1_length;++i)31         arr[i][0]=0;32 33     for(int i=1;i<s1_length;++i)34         for(int j=1;j<s2_length;++j)35             if(s1[i]==s2[j])36             {37                 arr[i][j]=arr[i-1][j-1]+1;38                 pre[i][j]=UP_LEFT;39             }40             else41             {42                 if(arr[i-1][j]==arr[i][j-1])43                 {44                     arr[i][j]=arr[i-1][j];45                     pre[i][j]=LEFTORUP;46                 }47                 else if(arr[i-1][j]>arr[i][j-1])48                 {49                     arr[i][j]=arr[i-1][j];50                     pre[i][j]=UP;51                 }52                 else53                 {54                     arr[i][j]=arr[i][j-1];55                     pre[i][j]=LEFT;56                 }57             }58 59     print_LCS(s1_length-1,s2_length-1);60 }61 62 void print_LCS(int i,int j)63 {64     if(i==0||j==0)65         return;66 67     if(pre[i][j]==UP_LEFT)68     {69         cout<<s1[i]<<‘\t‘;70         print_LCS(i-1,j-1);71     }72     else if(pre[i][j]==UP)73         print_LCS(i-1,j);74     else if(pre[i][j]==LEFT)75         print_LCS(i,j-1);76 }
View Code

以上情况中两个序列只存在一个LCS，但是若存在多个LCS应该怎么解决呢？

若序列s1：2,5,7,9,3,1,2

         s2：3,5,3,2,8,7,9

则LCS为：5,3,2; 2,7,9; 5,7,9

以上两个表格为算法的思路，上面表格为顺序思路，arr[i][j]表示s1(1:i) s2(1:j)两个序列的LCS长度，下面表格为回溯思路，从右下角开始根据方向得到LCS，其中数字意义为：

 LEFT=1;
 UP=2;
 UP_LEFT=3;
 LEFTORUP=4;顺序时由上面或左面数字得到（区别于只有一个LCS存在），目的在于回溯时可以得到序列所有的LCS，代码还没有实现。

 


联系
我们