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

一时失言乱红尘 2024-04-18 19:12 0阅读 0赞

文件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;
    }