最长公共子序列-C++/C-蒲公英云

最长公共子序列-C++/C

文件main.c
#include <iostream>
#include <string.h>
#include <stdio.h>
#include "LCSLLength.h"
using namespace std;
int main(){
    char * x="ABCBDAB";
    char * y="BDCABA";
    LCSLLength L1(y,x);
    cout<<"L1.getLength() = "<<L1.getLength()<<endl;
    char *res=L1.getLCS();
    printf("\n%s\n",res);
    cout<<"\nhello world!!\n";
    return 0;
}
文件.h
#ifndef LCSLLENGTH_H
#define LCSLLENGTH_H
#include <iostream>
using namespace std;
class LCSLLength
{
    public:
        LCSLLength(char * x, char * y);
        virtual ~LCSLLength();
        int getLength();
        char* getLCS();
    protected:
    private:
        char *x;
        char *y;
        int size_x=0;
        int size_y=0;
        int flag[500][500];
};
#endif // LCSLLENGTH_H

文件.cpp

#include "LCSLLength.h"
#include "stdio.h"
#include "stdlib.h"
LCSLLength::LCSLLength(char *x , char *y)
{
    this->x = x;
    this->y = y;
    printf("%s\n",this->x);
    printf("%s\n",this->y);
    while(this->x[size_x]!='\0'){
        size_x++;
    }
    while(this->y[size_y]!='\0'){
        size_y++;
    }
    cout<<"x="<<size_x<<" and y="<<size_y<<endl;
}
LCSLLength::~LCSLLength()
{
    //dtor
}
//返回最长公共子序列长度, x,y
int LCSLLength::getLength(){
    printf("%s\n",x);
    printf("%s\n",y);
    int array[size_x+1][size_y+1]={0};  //保存标记
    int data[size_x+1][size_y+1]={0};   //保存长度
    for(int i=0; i<=size_x; i++){
        for(int j=0; j<=size_y; j++){
            if(i==0 || j==0){
                data[i][j]=0;
                array[i][j]=0;
            }
            else if(x[i-1] == y[j-1]){
//                    cout<<data[i-1][j-1]<<endl;
                data[i][j]=data[i-1][j-1]+1;
                array[i][j]=1;
            }
            else if(data[i-1][j] >= data[i][j-1]){
                data[i][j]=data[i-1][j];
                array[i][j]=3;
            }
            else{
                data[i][j]=data[i][j-1];
                array[i][j]=2;
            }
        }
    }
    cout<<"数组data"<<endl;
    for(int i=0; i<=size_x; i++){
        for(int j=0; j<=size_y; j++){
            cout<<data[i][j]<<"  ";
            flag[i][j] = array[i][j];
        }
        cout<<endl;
    }
    cout<<"数组array"<<endl;
    for(int i=0; i<=size_x; i++){
        for(int j=0; j<=size_y; j++){
            cout<<array[i][j]<<"  ";
        }
        cout<<endl;
    }
    return data[size_x][size_y];
}
char* LCSLLength::getLCS()
{
    char res[500];
    int i = size_x;
    int j = size_y;
    int k = 0;    ///用于保存结果的数组标志位
    while (i>0 && j>0)
    {
        if (flag[i][j] == 1)   ///如果是对角线标记
        {
            res[k] = x[i - 1];
            k++;
            i--;
            j--;
        }
        else if (flag[i][j] == 2)  ///如果是向左标记
        {
            j--;
        }
        else if (flag[i][j] == 3)  ///如果是向上标记
        {
            i--;
        }
    }
    printf("ok\n");
    char result[size_x+size_y];
    int a=0;
    for (i = k - 1; i >= 0; i--){
        result[a++]=res[i];
        printf("%c", res[i]);
    }   result[a]='\0';
    return result;
}