对于最长公共子序列的动静布局算法剖析
-
示例引出：
- 给定序列 \(X = \{A, B, C, B, D, A, B\} \)和 \(Y = \{B, D, C, A, B, A\} \)，要求找出它们的最长公共子序列。
-
什么是子序列？
- 简略来说，就是从某个给定的序列中，依照从左向右的程序提取出某些元素形成的序列。
- 那么对于上述示例中的 \(X \)来说，\(\{B, C, D, B\} \)就是其中的一个子序列.
- 那么最长公共子序列就是求两个序列中最长雷同的子序列，对于上述示例来说，\(\{B,C,B,A\},\{B,D,A,B\},\{B,C,A,B\} \)是两者的最长公共子序列。
-
构造剖析：
- 最长公共子序列具备最优子结构的性质：某个问题的最优解蕴含其子问题的最优解。
- 这里给出递推关系：
- 假如序列 \(X_n=\{x_1, x_2,…,x_n\} \)和序列 \(Y_m=\{y_1,y_2,..,,y_m\} \)，而两者的最长公共子序列 \(Z_k=\{z_1,z_2,…,z_k\} \)；
-
那么：
- 当 \(x_n=y_m \)时，有 \(z_k=x_n=y_m\)，\(z_{k-1} \)为 \(x_{n-1} \)和 \(y_{m-1} \)的最长公共子序列；
- 当 \(x_n\neq y_m \)且 \(z_k=y_m \)时，\(z_{k-1} \)为 \(x_n \)和 \(y_{m-1} \)的最长公共子序列；
- 当 \(x_n\neq y_m \)且 \(z_k=x_n \)时，\(z_{k-1} \)为 \(x_{n-1} \)和 \(y_{m} \)的最长公共子序列.
-
能够给出递归关系：
- 这里应用
c[i][j]来存储序列 \(X_i \)和序列 \(Y_j \)的最长公共子序列， - $$c[i][j]=\begin{cases}0,\ \ i>0;\ j=0\\c[i-1][j-1]+1,\ \ i,j>0;\ x_i=y_j\\max(c[i-1][j],c[i][j-1]),\ \ i,j>0;\ x_i\neq y_j \end{cases}$$
- 这里给出上述示例的最大长度计算图示，右边是长度数组，左边是标记数组：
- 这里咱们能够看到，二维数组中最大值为 4，阐明咱们的最长公共子序列的长度为 4。
- 而咱们能够记录下长度最大的坐标，并从此进行查问。
- 如上图中左边的局部，对于 (7, 6) 来说，因为
c[6][6] = c[7,5]，所以须要同时向上和向下查问，之后的依照如上规定查问即可。 - 这里再给出另外一条查问线路，如下图：
- 这里给出实现代码如下，为了防止反复编写比拟代码，这里应用了标记数组
b[n+1][m+1]来批示回溯方向： -
#include <iostream> #include <vector> using namespace std; const int maxn = 100; vector<int> temp; /** * @description: 获取最长公共子序列的长度 * @param {int} n: 序列 X 的长度 * @param {int} m: 序列 Y 的长度 * @param {char*} x: 序列 X，索引从 1 开始到 n 完结 * @param {char*} y: 序列 Y，索引从 1 开始到 m 完结 * @param {int**} c: 长度二维数组, 大小为(m + 1) * (n + 1) * @param {int**} b: 标记二维数组, 大小为(m + 1) * (n + 1) * @return {int} 最长公共子序列的长度 */ int Longest_Common_SubSequence_Length(int n, int m, char *x, char *y, int **c, int **b) {for(int i = 0; i <= n; i++) {c[i][0] = 0; } for(int j = 0; j <= m; j++) {c[0][j] = 0; } for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {if(x[i] == y[j]) {c[i][j] = c[i-1][j-1] + 1; b[i][j] = 1; } else if(c[i][j-1] > c[i-1][j]) {c[i][j] = c[i][j-1]; b[i][j] = 2; } else if(c[i][j-1] < c[i-1][j]) {c[i][j] = c[i-1][j]; b[i][j] = 3; } else if(c[i][j-1] == c[i-1][j]) {c[i][j] = c[i-1][j]; b[i][j] = 4; } } } return c[n][m]; } /** * @description: 输入最长公共子序列 * b[i][j] = 1, 入栈，再向 (i-1, j-1) 查找 * b[i][j] = 2, 向 (i, j-1) 查找 * b[i][j] = 3, 向 (i-1, j) 查找 * b[i][j] = 4, 向 (i-1, j) 和(i, j-1)同时查找 */ void LCS(char *x, int **b, int i, int j, int longest) {if(i == 0 || j == 0) {if(temp.size() == longest) {for(int i = temp.size() - 1; i >= 0; i--) {printf("%c",x[temp[i]]); } printf("\n"); } return ; } if(b[i][j] == 1) {temp.push_back(i); LCS(x, b, i-1, j-1, longest); temp.pop_back();} else if(b[i][j] == 2) {LCS(x, b, i, j-1, longest); } else if(b[i][j] == 3) {LCS(x, b, i-1, j, longest); } else {LCS(x, b, i-1, j, longest); LCS(x, b, i, j-1, longest); } } int main(void) { int n, m; int **c, **b; char x[maxn], y[maxn]; scanf("%d%d", &n, &m); c = (int **) malloc(sizeof(int*) * (n+1)); b = (int **) malloc(sizeof(int*) * (n+1)); for(int i = 0; i <= n; i++) {c[i] = (int *)malloc(sizeof(int) * (m+1)); b[i] = (int *)malloc(sizeof(int) * (m+1)); } scanf("%s",(x+1)); scanf("%s",(y+1)); Longest_Common_SubSequence_Length(n, m, x, y, c, b); LCS(x, b, n, m, c[n][m]); } -
输出测试：
7 6 ABCBDAB BDCABA -
输入后果：
B C B A B C A B B D A B - 算法复杂度剖析：
- 计算最长公共子序列长度：在
int Longest_Common_SubSequence_Length(int n, int m, char *x, char *y, int **c, int **b)中，对于每个单元c[i][j]来说，计算消耗工夫为 \(O(1) \)，总计工夫复杂度为 \(O(n*m) \)。 - 获取最长公共子序列：在
void LCS(char *x, int **b, int i, int j, int longest)中回溯寻找某一个最大公共子序列的比拟次数最大为 m +n，工夫复杂度为 \(O(n+m) \)。 - 这里咱们应用了标记数组来防止反复编写比拟代码，咱们也能够不应用标记数组，这样能够节俭肯定的空间。同时，如果咱们只是为了失去最长公共子序列的长度，咱们能够将空间复杂度缩小到 \(O(min(n,m)) \)，因为在之前的计算中能够发现，咱们只须要保留数组
c中的第 \(i \)行和第 \(i-1 \)行的数据即可。
- 这里应用