最长公共子序列
- 描述
- 咱们就不拐弯抹角了，如题，需要你做的就是写一个程序，得出最长公共子序列。
tip：最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。
- 输入
- 第一行给出一个整数N(0<N<100)表示待测数据组数
接下来每组数据两行，分别为待测的两组字符串。每个字符串长度不大于1000. - 输出
- 每组测试数据输出一个整数，表示最长公共子序列长度。每组结果占一行。
- 样例输入
-
2 asdf adfsd 123abc abc123abc
- 样例输出
-
3 6
- 来源
- 经典
- 上传者
- hzyqazasdf
// 题目36优秀代码--运行号：785599 // 运行时间：2014-03-28 19:26:38 | 编程语言:C/C++ | 运行人:MrMoGu
#include <stdio.h> #include <string.h> char s1[1001], s2[1001]; int dp[1001], t, old, tmp; int main(){ scanf("%d", &t); getchar(); while(t--){ gets(s1); gets(s2); memset(dp, 0, sizeof(dp)); int lenS1=strlen(s1), lenS2=strlen(s2); for(int i=0; i<lenS1; i++){ old=0; //若s1[i]==s2[j], dp[i][j] = dp[i-1][j-1]+1 //否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1]) //此处进行了空间优化，old 代表 dp[i-1][j-1] //dp[j-1] 代表 dp[i][j-1], dp[j] 代表 dp[i-1][j] for(int j=0; j<lenS2; j++){ tmp = dp[j]; if(s1[i]==s2[j]) dp[j] = old+1; else if(dp[j-1]>dp[j])dp[j]=dp[j-1]; old = tmp; } } printf("%d ", dp[lenS2-1]); } return 0; }
// 查看代码---运行号：1186649----结果：Accepted // 运行时间：2015-03-09 15:49:36 | 运行人:1306405026 #include <stdio.h> #include <cstring> #include <iostream> #include <vector> #include <algorithm> using namespace std; int n,m; const int CHAR = 256; const int maxn = 1010; int ans[maxn*maxn]; int dp[maxn*maxn]; char S[maxn]; vector<int>v[CHAR]; int er(int l,int r,int x) { while(l<=r) { int mid = (l+r)/2; if( ans[mid] >= x ) r = mid - 1; else l = mid + 1; } return l; } int main() { scanf("%d",&n); while( n-- ) { for(int i=0 ; i<CHAR ; i++) v[i].clear(); scanf("%s",S); int l = strlen(S); for(int i=l-1 ; i>=0 ; i-- ) { v[ S[i] ].push_back(i); ///S[i]字符在字符串对应的位置 ///cout << S[i] << " " << v[ S[i] ].size() << endl; } int x = 0; scanf("%s",S); l = strlen(S); for(int i=0 ; i<l ; i++ ){ int k = v[ S[i] ].size(); if( k ) { for(int j=0 ; j<k ; j++ ) { dp[x++] = v[ S[i] ][j]; } } } m = 0; ans[m] = -1<<30; for(int i=0; i<x ; i++) { int x = er(0,m,dp[i]); ans[x] = dp[i]; if( x == m+1 ) m++; } printf("%d ",m); } return 0; }
最长公共子序列一般性总结:
问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列<i0，i1，…，ik-1>，使得对所有的j=0，1，…，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。
考虑最长公共子序列问题如何分解成子问题，设A=“a0，a1，…，am-1”，B=“b0，b1，…，bm-1”，并Z=“z0，z1，…，zk-1”为它们的最长公共子序列。不难证明有以下性质：
（1） 如果am-1=bn-1，则zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一个最长公共子序列；
（2） 如果am-1!=bn-1，则若zk-1!=am-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列；
（3） 如果am-1!=bn-1，则若zk-1!=bn-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列。
这样，在找A和B的公共子序列时，如有am-1=bn-1，则进一步解决一个子问题，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一个最长公共子序列；如果am-1!=bn-1，则要解决两个子问题，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列，再取两者中较长者作为A和B的最长公共子序列。
求解：
引进一个二维数组c[][]，用c[i][j]记录X[i]与Y[j] 的LCS 的长度，b[i][j]记录c[i][j]是通过哪一个子问题的值求得的，以决定搜索的方向。
我们是自底向上进行递推计算，那么在计算c[i,j]之前，c[i-1][j-1]，c[i-1][j]与c[i][j-1]均已计算出来。此时我们根据X[i] = Y[j]还是X[i] != Y[j]，就可以计算出c[i][j]。
问题的递归式写成：
回溯输出最长公共子序列过程：
算法分析：
由于每次调用至少向上或向左（或向上向左同时）移动一步，故最多调用(m + n)次就会遇到i = 0或j = 0的情况，此时开始返回。返回时与递归调用时方向相反，步数相同，故算法时间复杂度为Θ(m + n)。
#include <stdio.h> #include <string.h> #define MAXLEN 100 void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN], int b[][MAXLEN]) { int i, j; for(i = 0; i <= m; i++) c[i][0] = 0; for(j = 1; j <= n; j++) c[0][j] = 0; for(i = 1; i<= m; i++) { for(j = 1; j <= n; j++) { if(x[i-1] == y[j-1]) { c[i][j] = c[i-1][j-1] + 1; b[i][j] = 0; } 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; } } } } void PrintLCS(int b[][MAXLEN], char *x, int i, int j) { if(i == 0 || j == 0) return; if(b[i][j] == 0) { PrintLCS(b, x, i-1, j-1); printf("%c ", x[i-1]); } else if(b[i][j] == 1) PrintLCS(b, x, i-1, j); else PrintLCS(b, x, i, j-1); } int main(int argc, char **argv) { char x[MAXLEN] = {"ABCBDAB"}; char y[MAXLEN] = {"BDCABA"}; int b[MAXLEN][MAXLEN]; int c[MAXLEN][MAXLEN]; int m, n; m = strlen(x); n = strlen(y); LCSLength(x, y, m, n, c, b); PrintLCS(b, x, m, n); return 0; }