最长公共子序列——输出

首先我不得不说这道题,你要先求公共子序列的长度......然后去DFS一遍注意要倒着搜......公共子序列也要倒着找..........我做了好久，然后老师要卡我，所以我又花了好久记录大小写.......代码：

#include<bits/stdc++.h>
using namespace std;
char a[1001],b[1001];
int dp[1001][1001]={0};
int n1,n2,sum=0;
int ans[1001]={0};
int a1[1001][101],b1[1001][101];
int mark[11000],mark2[11000];
int k=0,k2=0;
bool pd=false;
void dfs(int ji_lu,int x,int y)
{
    if(pd==true) return ;//判断输出了吗
    if(ji_lu==0)//如果它的最长公共子序列的数为零
    {
        pd=true;
        for(int i=0;i<k2;i++)
        {
            if(mark[i]==1) cout<<char(ans[i]+97);//特判 
            else if(mark[i]==0) cout<<char(ans[i]+65);//输出
        }
        return ;
    }
    for(int i=0;i<26;i++)//枚举26个字母
    {
        int a2=a1[x][i],b2=b1[y][i];
        if(dp[a2+1][b2+1]==ji_lu&&a[a2]==b[b2])//去找第一个相等的字母
        {
            ans[k++]=i;//记录
            if(a[a2]>='a'&&a[a2]<='z') mark[k2++]=1;//记录小写 
            else mark[k2++]=0;//记录大写 
            dfs(ji_lu-1,a2-1,b2-1);//在搜一遍
            k--;//回溯
        }
    }
}
int main()
{
    memset(mark,-1,sizeof(mark));//赋初值 
    cin>>a>>b;
    n1=strlen(a);
    n2=strlen(b);
    for(int i=0;i<n1/2;i++) swap(a[i],a[n1-i-1]);//将这个串倒过来
    for(int i=0;i<n2/2;i++) swap(b[i],b[n2-i-1]);
    for(int i=1;i<=n1;i++)//最长公共子序列
    {
        for(int j=1;j<=n2;j++)
        {
            if(a[i-1]==b[j-1])
            {
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    memset(a1,-1,sizeof(a1));
    memset(b1,-1,sizeof(b1));
    for(int i=0;i<n1;i++)
    {
        for(int j=i;j>=0;j--)
        {
            if(a[j]>='a'&&a[j]<='z')
            {
                if(a1[i][a[j]-'a']==-1)
                {
                    a1[i][a[j]-'a']=j;
                }
            }    
            else
            {
                if(a1[i][a[j]-'A']==-1)//找这个字母出现在第几个
                {
                    a1[i][a[j]-'A']=j;
                }
            }
        }
    }
    for(int i=0;i<n2;i++)
    {
        for(int j=i;j>=0;j--)
        {
            if(b[j]>='a'&&b[j]<='z')
            {
                if(b1[i][b[j]-'a']==-1)
                {
                    b1[i][b[j]-'a']=j;
                }
            }
            else
            {
                if(b1[i][b[j]-'A']==-1)
                {
                    b1[i][b[j]-'A']=j;
                }
            }
        }
    }
    dfs(dp[n1][n2],n1-1,n2-1);//搜索
}