首页 > 代码库 > 最长公共子序列--【算法导论】
最长公共子序列--【算法导论】
最长公共子序列:一个序列 S 。假设各自是两个或多个已知序列的子序列,且是全部符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。
其核心非常easy:
这样,构造子结构就比較简单了:
if(str1[i - 1] == str2[j - 1])
m[i][j] = m[i - 1][j - 1] + 1;
else
m[i][j] = max(m[i - 1][j], m[i][j - 1]);
前面动态规划思想说得足够了,这次直接贴:
#include <iostream> #include <cstring> using namespace std; void Print(int **m, int lena, int lenb, char *str1) { //int length = m[lena][lenb]; if(0 == lena || 0 == lenb) return ; else if(m[lena][lenb] == m[lena - 1][lenb - 1] + 1) { Print(m, lena - 1, lenb - 1, str1); cout << str1[lena - 1]; } else if(m[lena - 1][lenb] > m[lena][lenb - 1]) Print(m, lena, lenb - 1, str1); else Print(m, lena - 1, lenb, str1); } int Lcs(char *str1, char *str2) { int lena = strlen(str1); int lenb = strlen(str2); int **m = new int*[lena + 1]; for(int i = 0; i < lena + 1; i++) m[i] = new int[lenb + 1]; for(int i = 0; i < lena + 1; i++) { for(int j = 0; j < lenb + 1; j++) m[i][j] = 0; } for(int i = 1; i < lena + 1; i++) { for(int j = 1; j < lenb + 1; j++) { if(str1[i - 1] == str2[j - 1]) m[i][j] = m[i - 1][j - 1] + 1; else m[i][j] = max(m[i - 1][j], m[i][j - 1]); } } for(int i = 0; i < lena + 1; i++) { for(int j = 0; j < lenb + 1; j++) cout << m[i][j] << " "; cout << endl; } Print(m, lena, lenb, str1); return m[lena][lenb]; } int main() { char str1[] = "ACBDCDB"; char str2[] = "ADCBEB"; cout << endl << Lcs(str1, str2) << endl; return 0; }
上述输出分别为匹配的二维数组结果,最长公共子序列(当中之中的一个),长度;
O(∩_∩)O(不足之处请不吝赐教)
最长公共子序列--【算法导论】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。