#include "stack.h"
#include <iostream>
using namespace std;
#define M 8
#define N 7
Stack s;
int count = 0; //用于记录lcs的个数
void lcs(char x[M],char y[N],int c[M][N],int b[M][N]){
int i,j;
for(i=0;i<M;i++){ //初始化c[][0]
c[i][0] = 0;
b[i][0] = 0;
}
for(j=0;j<N;j++){ //初始化c[0][]
c[0][j] = 0;
b[0][j] = 0;
}
for(i=1;i<M;i++){
for(j=1;j<N;j++){
if(x[i] == y[j]){ //x=y
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = 1;
}
else{ //x!=y
if(c[i-1][j] > c[i][j-1]){
c[i][j] = c[i-1][j];
b[i][j] = 2;
}
else if(c[i-1][j] < c[i][j-1]){
c[i][j] = c[i][j-1];
b[i][j] = 3;
}
else if(c[i-1][j] == c[i][j-1]){
c[i][j] = c[i-1][j];
b[i][j] = 4;
}
}
}
}
//输出c
cout<<"LCS的长度:"<<endl;
for(i=0;i<M;i++){
for(j=0;j<N;j++){
cout<<c[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
//输出b
cout<<"搜索方向:"<<endl;
for(i=0;i<M;i++){
for(j=0;j<N;j++){
cout<<b[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
}
void lcs_output(int b[M][N],int clength,char x[M],int i,int j){
if(i == 0 || j == 0){
if(count == clength){
count = 0;
}
return;
}
else{
if(b[i][j] == 1){
s.push(x[i]);
count++;
lcs_output(b,clength,x,i-1,j-1);
}
else if(b[i][j] == 2){
lcs_output(b,clength,x,i-1,j);
}
else if(b[i][j] == 3){
lcs_output(b,clength,x,i,j-1);
}
else if(b[i][j] == 4){
//如果之前有走的同样的路径,则将它们暂时放到一个数组里。然后向上走。
char temp[4];
for(int k=0;k<count;k++){
temp[k] = s.get(k);
}
lcs_output(b,clength,x,i-1,j);
//待构成一个LCS后,将临时数组的数据压入栈,然后从左走
if(k>0){
for(int n=k-1;n>=0;n--){
s.push(temp[n]);
}
}
lcs_output(b,clength,x,i,j-1);
}
}
}
int main(){
char x[M] = {'x','a','b','c','b','d','a','b'}; //x序列
char y[N] = {'y','b','d','c','a','b','a'}; //y序列
int c[M][N]; //c记录x,y的lcs长度
int b[M][N]; //b记录搜索方向,1代表斜向上,2代表向上,3代表向左,4代表左和上
lcs(x,y,c,b);
lcs_output(b,c[M-1][N-1],x,M-1,N-1);
cout<<"所有LCS如下:"<<endl;
int ccc = 0;
while(!s.empty()){
cout<<s.pop()<<" ";
ccc++;
if(ccc % 4 == 0){
cout<<endl;
}
}
return 0;
}