#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
void LCSLength(int m, int n, char x[100], char y[100], int c[100][100], int b[100][100]);
void LCS(int m,int n ,char x[100], char y[100],int c[100][100]);
char p[100][100][100];
char r[100][100][100];
int count_num_r = 0;
int count_num_c = 0;
int count_p;
int _row[100];
int _col[100];
int start = 0;
int endx = 0;
vector<char>vec;
vector<int>vec_x;
map<int, char>mp;
map<int, char>temp;
char x[100];
char y[100];
int c[100][100];
int b[100][100];
int i=0;
int j=0;
int main() {
string X;
string Y;
cout<<"请输入X序列：";
cin>>X;
cout<<"请输入Y序列：";
cin>>Y;
int X_len=X.size();
int Y_len=Y.size();
//把输入的字符串X存入到char型的数组x里面
memcpy(x, X.c_str(), X.length());
//把输入的字符串Y存入到char型的数组y里面
memcpy(y, Y.c_str(), Y.length());
LCSLength(X_len, Y_len, x, y, c, b);
//c矩阵中，行列数从0开始数，比如第2行第1列的值为1，表示X序列有2个元素AB，Y序列有1个元素B 的时候，最长公共子序列有1个
cout << "c矩阵:" << endl;
for (int i = 0;i <= X_len;i++) {
for (int j = 0;j <= Y_len;j++) {
cout << c[i][j]<<"\t";
}
cout << endl<<endl;
}
cout << endl << endl;
//因为该方法为非递归，所以用不上b矩阵
// cout << "b矩阵：" << endl;
// for (int i = 1;i <= X_len;i++) {
// for (int j = 1;j <= Y_len;j++) {
// cout << b[i][j] << "\t";
// }
// cout << endl<<endl;
// }
LCS(X_len, Y_len, x, y, c);
cout << endl << endl;
}
void LCSLength(int m, int n, char x[100], char y[100], int c[100][100], int b[100][100]) {
int i, j;
for (i = 1;i <= m;i++) {
c[i][0] = 0;
}
for (i = 1;i <= n;i++) {
c[0][i] = 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] = 1;
}
else if (c[i-1][j]>=c[i][j-1]) {
c[i][j] = c[i - 1][j];
// b[i][j] = 2;
}
else {
c[i][j] = c[i][j - 1];
// b[i][j] = 3;
}
}
}
}
void LCS(int m,int n,char x[100],char y[100],int c[100][100]) {
for (int i = 1;i <= m;i++) {
for (int j = 1;j <= n;j++) {
if ((c[i][j]==c[i-1][j]+1) && (c[i][j]==c[i][j - 1]+1) && (c[i][j]==c[i-1][j-1]+1)) {
p[(c[i][j])][i][j] = x[i-1];
}
}
}
for (int k = 1;k <= c[m][n];k++) {
for (int i = 1;i <= m;i++) {
for (int j = 1;j <= n;j++) {
if (p[k][i][j]!='\000') {
_row[count_p] = i;
_col[count_p] = j;
count_p++;
if (k == 1) {
start++;
}
else if (k==c[m][n]) {
endx++;
}
}
}
}
count_num_r = 0;
count_num_c = 0;
}
for (int i = 0;i < count_p;i++) {
mp[i] = 't';
}
for (int i = 0;i < count_p;i++) {
temp[i] = 't';
}
cout << "最长公共子序列为：" << endl;
for (int i = 0;i < start;i++) {
for (int i = 0;i < count_p;i++) {
temp[i] = 't';
mp[i] = 't';
}
int ii = i;
int j = ii+1;
vec.clear();
vec_x.clear();
vec.push_back(x[(_row[i]) - 1]);
vec_x.push_back(i);
while (vec.size()!=0&&vec_x.size()!=0) {
while (j < count_p) {
if ((_row[ii]<_row[j]) && (_col[ii]<_col[j])&&(mp[j]=='t')) {
ii = j;
j++;
vec.push_back(x[(_row[ii]) - 1]);
vec_x.push_back(ii);
for (int i = 0;i < mp.size();i++) {
mp[i] = 't';
}
}
else {
j++;
}
}
if (vec.size() == c[m][n]) {
for (int i = 0;i < c[m][n];i++) {
cout << vec[i] ;
}
cout << endl;
}
int vec_x_last = (vec_x[vec_x.size() - 1]);
temp[vec_x_last] = 'f';
for (int t = 0;t < count_p;t++) {
if (temp[t]=='f') {
mp[t]='f';
}
}
vec.pop_back();
vec_x.pop_back();
if (vec.size()!=0) {
ii = vec_x[vec_x.size() - 1];
j = ii + 1;
}
}
}
}
由于代码可读性比较差，所以这里只讲算法思想。
image.png
①如上图矩阵，行数和列数我们从0开始数，比如第6行第4列的值为3，意思是，X序列取6个元素“ABCBDA”，Y序列取4个元素“BDCA”，此时，两个序列的最长公共子序列的个数为3。
②我们发现，把每个不同的数字用红线隔离，每个角落画圈圈的数字就是答案存在的地方！而且画圈圈的地方所在的行和列对应的字母是一样的，这个字母就是答案之一。
③在画圈圈的数字中，以1，2，3，4的顺序走，而且要满足它们的行和列要单调递增，满足这两个条件的有3条路，这3条路就是构成最长公共子序列的答案。如上图可以得出答案 BCBA ，BCAB ，BDAB
重点来了。电脑不是人脑，通过矩阵，我们很容易看出，这3个答案是什么，但是，程序是如何实现的呢？
image.png
image.png
通过以上的原理，可以找到所有最长公共子序列的答案。
运行的时候我把矩阵输出注释掉了
image.png
image.png
如果输入 太长的序列，会导致无法输出结果，该程序时间代价太大了，有待改进
网友评论