LCS最长公共子序列C++实现

算法思路：动态规划

 

版本1：只输出公共长度

 

#include <iostream>
#include <string>
using namespace std;int c[1000][1000]; //c[i][j]用来存储 Xi到Yj的最长公共子序列长度 void MaxLength(int m, int n, string x, string y) { //m，n分别表示字符串x和字符串y的长度 int i, j; for (i = 0; i <= m; i++) // 当j为0的时候，空序列是Xi到Yj的最长公共子序列，所以赋值0，注意这里i从0开始c[i][0] = 0;for (i = 0; i <= n; i++) // 当x为0的时候，空序列是Xi到Yj的最长公共子序列，所以赋值0，注意这里i从0开始c[0][i] = 0;for (i = 1; i <= m; i++) {  for (j = 1; j <= n; j++) { if (x[i - 1] == y[j - 1]) {  // 索引要减1，因为字符串从0开始c[i][j] = c[i - 1][j - 1] + 1;} else {c[i][j] = max(c[i - 1][j], c[i][j - 1]); }}} 
}int main() {string x, y;cin >> x >> y;int m = x.length();  // 得到字符串x的长度 int n = y.length();   // 得到字符串y的长度 MaxLength(m, n, x, y); int precent = 0; if (c[m][n]!= 0) {precent = (c[m][n] * 100) / min(m, n);}cout << "公共长度:" << c[m][n] << endl; return 0;
}

版本2：输出长度，比较相似程度，输出公共序列

#include <iostream>
#include <string>
using namespace std;int c[1000][1000]; //c[i][j]用来存储 Xi到Yj的最长公共子序列长度 void MaxLength(int m, int n, string x, string y) { //m，n分别表示字符串x和字符串y的长度 int i, j; for (i = 0; i <= m; i++) // 当j为0的时候，空序列是Xi到Yj的最长公共子序列，所以赋值0，注意这里i从0开始c[i][0] = 0;for (i = 0; i <= n; i++) // 当x为0的时候，空序列是Xi到Yj的最长公共子序列，所以赋值0，注意这里i从0开始c[0][i] = 0;for (i = 1; i <= m; i++) {  for (j = 1; j <= n; j++) { if (x[i - 1] == y[j - 1]) {  // 索引要减1，因为字符串从0开始c[i][j] = c[i - 1][j - 1] + 1;} else {c[i][j] = max(c[i - 1][j], c[i][j - 1]); }}} 
}void LCS(int i, int j, string x, string y) {if (i == 0 || j == 0) return;if (x[i - 1] == y[j - 1]) { LCS(i - 1, j - 1, x, y); cout << x[i - 1]; } else if (c[i - 1][j] >= c[i][j - 1]) {LCS(i - 1, j, x, y);} else {LCS(i, j - 1, x, y);}
}int main() {string x, y;cin >> x >> y;int m = x.length();  // 得到字符串x的长度 int n = y.length();   // 得到字符串y的长度 MaxLength(m, n, x, y); int precent = 0; if (c[m][n]!= 0) {precent = (c[m][n] * 100) / min(m, n);}cout << "公共长度:" << c[m][n] << endl; if (precent > 75) {cout << precent << "% " << "Yes,相似度高" << endl;} else {cout << precent << "% " << "No，相似度不高" << endl;}cout << "最长序列：" << endl; LCS(m, n, x, y);cout << endl;return 0;
}