编辑代码

#include<iostream>
#include<stack>
#include<string>
#include<cstring>
using namespace std;
void getLCS(string &str1, string &str2){
    int m = str1.length() + 1;
    int n = str2.length() + 1;
    int length[m][n];  
    int state[m][n]; 
    memset( state, 100, sizeof(state) );
    for(int i=0; i<m; i++){ 
        length[i][0] = 0;
    }
    for(int j=0; j<n; j++){
        length[0][j] = 0;
    }
    for(int i=1; i<m; i++){
        for(int j=1; j<n; j++){
            if(str1[i-1] == str2[j-1]) {
                length[i][j] = length[i-1][j-1] + 1;
                state[i][j] = 0;
            }else if(length[i][j-1] >= length[i-1][j]) {
                length[i][j] = length[i][j-1];
                state[i][j] = -1;  
            }else {
                length[i][j] = length[i-1][j];
                state[i][j] = 1;  
            }
        }
    }
    stack<char> lcs;
    for(int i=m-1, j=n-1; i>=0 && j>=0;){
        if(state[i][j] == 0){     
            lcs.push(str1[i-1]);
            i--;
            j--;
        }else if(state[i][j] == 1){
            i--; 
        }else{
            j--;
        }
    }
 
    if(lcs.empty()){
        cout<<"没有公共子序列"<<endl;
        return ;
    }
 
    cout<<"最长的子序列：";
    while(!lcs.empty()){
        cout<<lcs.top();
        lcs.pop();
    }
    cout<<"\n其长度为："<<length[m-1][n-1];
    
    return ;
}
 
int main(){
    string str1 = {"FOSHSTS"};
    string str2 = {"FOSSTSS"};
    cout<<"序列1："<<str1<<endl;
    cout<<"序列2："<<str2<<endl;
    getLCS(str1,str2);
 
    return 0;
}