首页 > 代码库 > 跟着编程之美学算法——最长公共子序列
跟着编程之美学算法——最长公共子序列
最长公共子序列是一个很经典的动态规划问题，最近正在学习动态规划，所以拿来这里再整理一下。
这个问题在《算法导论》中作为讲动态规划算法的例题出现。
动态规划，众所周知，第一步就是找子问题，也就是把一个大的问题分解成子问题。这里我们设两个字符串A、B，A = "a0, a1, a2, ..., am-1"，B = "b0, b1, b2, ..., bn-1"。
（1）如果am-1 == bn-1，则当前最长公共子序列为"a0, a1, ..., am-2"与"b0, b1, ..., bn-2"的最长公共子序列与am-1的和。长度为"a0, a1, ..., am-2"与"b0, b1, ..., bn-2"的最长公共子序列的长度+1。
（2）如果am-1 != bn-1，则最长公共子序列为max（"a0, a1, ..., am-2"与"b0, b1, ..., bn-1"的公共子序列，"a0, a1, ..., am-1"与"b0, b1, ..., bn-2"的公共子序列）
如果上述描述用数学公式表示，则引入一个二维数组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]的取值，按照上面的递推，求出c[i][j]，同时把路径记录在b[i][j]中（路径只有3中方向：左上、左、上，如下图）。
计算c[][]矩阵的时间复杂度是O(m*n)；根据b[][]矩阵寻找最长公共子序列的过程，由于每次调用至少向上或向左移动一步，这样最多需要（m+n）次就会i = 0或j = 0，也就是算法时间复杂度为O(m+n)。
一下是代码实现
1 #include <iostream> 2 #include <stdio.h> 3 #include <string> 4 #include <string.h> 5 6 using namespace std; 7 8 void LCS_Print(int **LCS_Direction, char *str, int row, int column) 9 { 10 if(str == NULL) 11 return; 12 13 int nLen1 = strlen(str); 14 15 if(nLen1 == 0 || row < 0 || column < 0) 16 return; 17 18 if(LCS_Direction[row][column] == 1) 19 { 20 if(row > 0 && column > 0) 21 LCS_Print(LCS_Direction, str, row - 1, column - 1); 22 printf("%c ", str[row]); 23 } 24 else if(LCS_Direction[row][column] == 2) 25 { 26 if(row > 0) 27 LCS_Print(LCS_Direction, str, row - 1, column); 28 } 29 else if(LCS_Direction[row][column] == 3) 30 { 31 if(column > 0) 32 LCS_Print(LCS_Direction, str, row, column - 1); 33 } 34 } 35 36 int LCS(char *str1, char *str2) 37 { 38 if(str1 == NULL || str2 == NULL) 39 return 0; 40 41 int nLen1 = strlen(str1); 42 int nLen2 = strlen(str2); 43 44 if(nLen1 <= 0 || nLen2 <= 0) 45 return 0; 46 47 // 申请一个二维数组，保存不同位置的LCS值 48 int **LCS_Length = new int*[nLen1]; 49 // 申请一个二维数组，保存公共序列的位置 50 int **LCS_Direction = new int*[nLen1]; 51 for(int i = 0; i < nLen1; i++) 52 { 53 LCS_Length[i] = new int[nLen2]; 54 LCS_Direction[i] = new int[nLen2]; 55 } 56 57 for(int i = 0; i < nLen1; i++) 58 LCS_Length[i][0] = 0; 59 for(int i = 0; i < nLen2; i++) 60 LCS_Length[0][i] = 0; 61 62 for(int i = 0; i < nLen1; i++) 63 { 64 for(int j = 0; j < nLen2; j++) 65 { 66 LCS_Direction[i][j] = 0; 67 } 68 } 69 70 cout<<"Init OK!"<<endl; 71 72 for(int i = 0; i <nLen1; i++) 73 { 74 for(int j = 0; j < nLen2; j++) 75 { 76 if(i == 0 || j == 0) 77 { 78 if(str1[i] == str2[j]) 79 { 80 LCS_Length[i][j] = 1; 81 LCS_Direction[i][j] = 1; 82 } 83 else 84 LCS_Length[i][j] = 0; 85 } 86 else if(str1[i] == str2[j]) 87 { 88 LCS_Length[i][j] = LCS_Length[i - 1][j - 1] + 1; 89 LCS_Direction[i][j] = 1; 90 } 91 else if(LCS_Length[i - 1][j] > LCS_Length[i][j - 1]) 92 { 93 LCS_Length[i][j] = LCS_Length[i - 1][j]; 94 LCS_Direction[i][j] = 2; 95 } 96 else 97 { 98 LCS_Length[i][j] = LCS_Length[i][j - 1]; 99 LCS_Direction[i][j] = 3;100 }101 }102 }103 104 LCS_Print(LCS_Direction, str1, nLen1 - 1, nLen2 - 1);105 cout<<endl;106 int nLCS = LCS_Length[nLen1 - 1][nLen2 - 1];107 for(int i = 0; i < nLen1; i++)108 {109 delete[] LCS_Length[i];110 delete[] LCS_Direction[i];111 }112 delete [] LCS_Length;113 delete [] LCS_Direction;114 return nLCS;115 }116 117 int main()118 {119 cout<<LCS("ABCBDAB", "BDCABA")<<endl;120 return 0;121 }复制代码
1 #include <iostream> 2 #include <stdio.h> 3 #include <string> 4 #include <string.h> 5 6 using namespace std; 7 8 void LCS_Print(int **LCS_Direction, char *str, int row, int column) 9 { 10 if(str == NULL) 11 return; 12 13 int nLen1 = strlen(str); 14 15 if(nLen1 == 0 || row < 0 || column < 0) 16 return; 17 18 if(LCS_Direction[row][column] == 1) 19 { 20 if(row > 0 && column > 0) 21 LCS_Print(LCS_Direction, str, row - 1, column - 1); 22 printf("%c ", str[row]); 23 } 24 else if(LCS_Direction[row][column] == 2) 25 { 26 if(row > 0) 27 LCS_Print(LCS_Direction, str, row - 1, column); 28 } 29 else if(LCS_Direction[row][column] == 3) 30 { 31 if(column > 0) 32 LCS_Print(LCS_Direction, str, row, column - 1); 33 } 34 } 35 36 int LCS(char *str1, char *str2) 37 { 38 if(str1 == NULL || str2 == NULL) 39 return 0; 40 41 int nLen1 = strlen(str1); 42 int nLen2 = strlen(str2); 43 44 if(nLen1 <= 0 || nLen2 <= 0) 45 return 0; 46 47 // 申请一个二维数组，保存不同位置的LCS值 48 int **LCS_Length = new int*[nLen1]; 49 // 申请一个二维数组，保存公共序列的位置 50 int **LCS_Direction = new int*[nLen1]; 51 for(int i = 0; i < nLen1; i++) 52 { 53 LCS_Length[i] = new int[nLen2]; 54 LCS_Direction[i] = new int[nLen2]; 55 } 56 57 for(int i = 0; i < nLen1; i++) 58 LCS_Length[i][0] = 0; 59 for(int i = 0; i < nLen2; i++) 60 LCS_Length[0][i] = 0; 61 62 for(int i = 0; i < nLen1; i++) 63 { 64 for(int j = 0; j < nLen2; j++) 65 { 66 LCS_Direction[i][j] = 0; 67 } 68 } 69 70 cout<<"Init OK!"<<endl; 71 72 for(int i = 0; i <nLen1; i++) 73 { 74 for(int j = 0; j < nLen2; j++) 75 { 76 if(i == 0 || j == 0) 77 { 78 if(str1[i] == str2[j]) 79 { 80 LCS_Length[i][j] = 1; 81 LCS_Direction[i][j] = 1; 82 } 83 else 84 LCS_Length[i][j] = 0; 85 } 86 else if(str1[i] == str2[j]) 87 { 88 LCS_Length[i][j] = LCS_Length[i - 1][j - 1] + 1; 89 LCS_Direction[i][j] = 1; 90 } 91 else if(LCS_Length[i - 1][j] > LCS_Length[i][j - 1]) 92 { 93 LCS_Length[i][j] = LCS_Length[i - 1][j]; 94 LCS_Direction[i][j] = 2; 95 } 96 else 97 { 98 LCS_Length[i][j] = LCS_Length[i][j - 1]; 99 LCS_Direction[i][j] = 3;100 }101 }102 }103 104 LCS_Print(LCS_Direction, str1, nLen1 - 1, nLen2 - 1);105 cout<<endl;106 int nLCS = LCS_Length[nLen1 - 1][nLen2 - 1];107 for(int i = 0; i < nLen1; i++)108 {109 delete[] LCS_Length[i];110 delete[] LCS_Direction[i];111 }112 delete [] LCS_Length;113 delete [] LCS_Direction;114 return nLCS;115 }116 117 int main()118 {119 cout<<LCS("ABCBDAB", "BDCABA")<<endl;120 return 0;121 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。