#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型的數(shù)組x里面
memcpy(x, X.c_str(), X.length());
//把輸入的字符串Y存入到char型的數(shù)組y里面
memcpy(y, Y.c_str(), Y.length());
LCSLength(X_len, Y_len, x, y, c, b);
//c矩陣中，行列數(shù)從0開始數(shù)，比如第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
①如上圖矩陣，行數(shù)和列數(shù)我們從0開始數(shù)，比如第6行第4列的值為3，意思是，X序列取6個元素“ABCBDA”，Y序列取4個元素“BDCA”，此時，兩個序列的最長公共子序列的個數(shù)為3。
②我們發(fā)現(xiàn)，把每個不同的數(shù)字用紅線隔離，每個角落畫圈圈的數(shù)字就是答案存在的地方！而且畫圈圈的地方所在的行和列對應(yīng)的字母是一樣的，這個字母就是答案之一。
③在畫圈圈的數(shù)字中，以1，2，3，4的順序走，而且要滿足它們的行和列要單調(diào)遞增，滿足這兩個條件的有3條路，這3條路就是構(gòu)成最長公共子序列的答案。如上圖可以得出答案 BCBA ，BCAB ，BDAB
重點來了。電腦不是人腦，通過矩陣，我們很容易看出，這3個答案是什么，但是，程序是如何實現(xiàn)的呢？
image.png
image.png
通過以上的原理，可以找到所有最長公共子序列的答案。
運行的時候我把矩陣輸出注釋掉了
image.png
image.png
如果輸入 太長的序列，會導(dǎo)致無法輸出結(jié)果，該程序時間代價太大了，有待改進(jìn)
