编辑代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int re[200][200];//记录路径数组1
int re1[200][200];//记录路径数组2
char s1[200],s2[200];//记录最长子序列数组1、2
int i1=0,i2=0;
void p(char t[],int n,int m){//根据记录路径数组1求最长子序列
if(m==0 || n==0) return;
    if(re[n][m]==0)//判断来源是否为左上角
    {
        p(t,n-1,m-1);//传参为左上角进行递归
        s1[i1]=t[n-1];
        i1++;
}
if(re[n][m]==1)//判断来源是否为上边
    p(t,n-1,m);//传参为上面一格进行递归
if(re[n][m]==2)//判断来源是否为左边
    p(t,n,m-1);//传参为左边一格进行递归
}
void p1(char t[],int n,int m){//根据记录路径数组2求最长子序列 与p相同
if(m==0 || n==0) return;
    if(re1[n][m]==0)
    {
        p1(t,n-1,m-1);
    s2[i2]=t[n-1];
    i2++;
}
 if(re1[n][m]==1)
    p1(t,n-1,m);
if(re1[n][m]==2)
    p1(t,n,m-1);

}
int main()
{
    int n,m,i,j,l=0,k;
    cin>>n>>m;
    getchar();
    char a[n],b[m];
    int z[n+1][m+1];//记录赋值数组
    //初始化赋值
    for(i=0;i<n+1;i++)//对第一列初始化
        z[i][0]=0;
    for(i=0;i<m+1;i++)//对第一行初始化
        z[0][i]=0;
    for(int i=0;i<n;i++)//分别输入字符串
    scanf("%c",&a[i]);
    getchar();
    for(int i=0;i<m;i++)
    scanf("%c",&b[i]);
    //对赋值数组进行判断和填充
    for(int i=1;i<n+1;i++)
        for(int j=1;j<m+1;j++)
    {
        if(a[i-1]==b[j-1])//判断行和列内容是否相同
        {
            z[i][j]=z[i-1][j-1]+1;//此格值等于左上角+1
            re[i][j]=0;//设0代表来源为左上角
        }
        else if(z[i-1][j]>z[i][j-1])//上面的值大于左面的
        {
            z[i][j]=z[i-1][j];//赋值为上面的值
            re[i][j]=1;//设1代表来源为上面
        }

        else //此时为左面的值大于等于上面的
            {z[i][j]=z[i][j-1];//赋值为左面的值
            re[i][j]=2;//设2代表来源为左面
        }
    }
    //下面这次遍历路径存储在re1数组里
    //与上面的区别是当上面和左面相等时取上面的值
    for(int i=1;i<n+1;i++)
        for(int j=1;j<m+1;j++)
    {
        if(a[i-1]==b[j-1])
        {
            re1[i][j]=0;//左上角
        }
        else if(z[i-1][j]>=z[i][j-1])//这里的判定条件不同
        {
            re1[i][j]=1;//上面
        }

        else {
            re1[i][j]=2;//左面
        }
    }
    //输出赋值数组
     for(i=1;i<n+1;i++)
        {
             for(j=1;j<m+1;j++)
                printf("%d ",z[i][j]);
             printf("\n");
        }
        printf("\n");
       p(a,n,m);
       p1(a,n,m);
       for(i=0;i<i1;i++)
       {
           if(s1[i]!=s2[i]){//判断两种判定条件下所得最长公共子序列是否相同
            k=1;break;
           }
       else k=0;
       }
           if(k==1)
           {//不相同则全部输出
               for(j=0;j<i1;j++)
                printf("%c ",s1[j]);
               printf("\n");
               for(j=0;j<i2;j++)
                printf("%c ",s2[j]);
           }
           else
            for(j=0;j<i1;j++)
                printf("%c ",s1[j]);
       printf("\n");
    return 0;
}