LCS（Longest Common Subsequence 最长公共子序列）

最长公共子序列

英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。而最长公共子串(要求连续)和最长公共子序列是不同的

应用

最长公共子序列是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。简而言之，百度知道、百度百科都用得上。

动态规划

第一步：先计算最长公共子序列的长度。

第二步：根据长度，然后通过回溯求出最长公共子序列。

现有两个序列X={x₁,x₂,x_3，...x_i}，Y={y₁,y₂,y_3，....，y_i}，

设一个C[i,j]: 保存X_i与Y_j的LCS的长度。

递推方程为：

代码亲测:

 1 #include <bits/stdc++.h>
 2 const int MAX=1010;
 3 char x[MAX];
 4 char y[MAX];
 5 int DP[MAX][MAX];
 6 int b[MAX][MAX];
 7 using namespace std;
 8 
 9 int PRINT_LCS(int b[][MAX],char *x,int i,int j)
10 {
11     if(i==0||j==0)
12         return 1;
13     if(b[i][j]==1)
14     {
15         PRINT_LCS(b,x,i-1,j-1);
16         cout<<x[i]<<" ";
17     }
18     else if(b[i][j]==2)
19     {
20         PRINT_LCS(b,x,i-1,j);
21     }
22     else if(b[i][j]==3)
23     {
24         PRINT_LCS(b,x,i,j-1);
25     }
26 
27 }
28 int main()
29 {
30     int T;
31     int n,m,i,j;
32     cin>>T;
33     while(T--)
34     {
35         while(cin>>n>>m)
36         {
37             for(int i=1; i<=n; i++)
38                 cin>>x[i];
39             for(int j=1; j<=m; j++)
40                 cin>>y[j];
41             memset(DP,0,sizeof(DP));
42             for(i=1; i<=n; i++)
43             {
44                 for(j=1; j<=m; j++)
45                 {
46                     if(x[i]==y[j])
47                     {
48                         DP[i][j]=DP[i-1][j-1]+1;
49                         b[i][j]=1;
50                     }
51 
52                     else if(DP[i-1][j]>=DP[i][j-1])
53                     {
54                         DP[i][j]=DP[i-1][j];
55                         b[i][j]=2;
56                     }
57                     else
58                     {
59                         DP[i][j]=DP[i][j-1];//Max(DP[i-1][j],DP[i][j-1]);
60                         b[i][j]=3;
61                     }
62                 }
63             }
64             cout<<DP[n][m]<<endl;
65             PRINT_LCS(b,x,n,m);
66             cout<<endl;
67         }
68     }
69     return 0;
70 }

View Code