编辑代码

#include <iostream>
#include <cstring>
using namespace std;
const int N=1024;
int c[N][N];
int maxLen=0,flag=0;
char s1[N],s2[N];
int len1,len2;
void LCSs()
{
    for(int i = 1; i <= len1; i++){
        for(int j = 1; j <= len2; j++){
            if(s1[i-1] == s2[j-1]){ //s1与s2序列是从s1[0]与s2[0]开始的
                c[i][j] = c[i-1][j-1] + 1;
                if(c[i][j] > maxLen){
                    maxLen = c[i][j];
                    flag = j;   //flag在s2中寻找应该从s2[flag-maxLen]-s2[flag-1]寻找
                }
            }
            else{
                c[i][j] = 0;
            }

        }
    }
}

void LCSs_PRINT(int flag,int maxLen,int len2 )
{
    if(flag==0 || maxLen==0){
        return;
    }
    for(int i = flag-maxLen; i < flag; i++){
        cout << s2[i];
    }
}

int main()
{
    cout<<"输入第一个字符串"<<endl;
    cin>>s1;
    cout<<"输入第二个字符串"<<endl;
    cin>>s2;
    len1 = strlen(s1);
    len2 = strlen(s2);
    for(int i = 0; i <= len1; i++){
        c[i][0] = 0;
    }
    for(int j = 0; j <= len2; j++){
        c[0][j] = 0;
    }
    LCSs();
    cout << "两个字符串的最长公共子序列的长度是：" << maxLen <<endl;
    cout << "两个字符串的最长公共子序列是：";
    LCSs_PRINT(flag,maxLen,len2);
    return 0;
}