9.3 Subsequence 2

Longest common subsequence problem (最长公共子串)
如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子串。注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。请编写一个函数，输入两个字符串，求它们的最长公共子序列，并打印出最长公共子序列。

例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共子序列，则输出BDAB。

当然这里，我们也是要先找递归的。假设我的两个sequence，一个是X，长度为n；另一个是Y，长度为m。 现在假设我有两个point，一个是i，指在X的最后一个元素上，另一个是j，指在Y的最后一个元素上。我们的递归应该是分三种情况的。
1.如果X[i] == Y[j] 那么LCS(X[i],Y[j]) = X[i] + LCS(X[i-1],Y[j-1])
这个很明显，因为发现了一组公共元素，就看剩下的有多少公共元素。
2.如果X[i] != Y[j] 那么 LCS(X[i],Y[j]) = max_len( LCS(X[i-1], Y[j]), LCS(X[i], Y[j-1]) )
这个其实也很容易相同，就是如果发现不同的，就去掉X或Y的最后一个，然后和另一个完整的比较，这样去掉X还是Y的最后一个，就有两种可能，所以就是要找中间max的一个。
3.如果 i=0 或者 j=0，就return ''
因为有一个sequence已经完了。

EXAMPLE INPUT

BDCABA
ABCBDAB

EXAMPLE OUTPUT

BDAB

主程序 (不能修改)

struct Result
{
    char LCS[100];
};

#include "source.c"

#include <stdio.h>

int main() {
    char text1[100];
    char text2[100];
    scanf("%s", text1);
    scanf("%s", text2);
    
    struct Result result = LCS(text1, text2);
    printf("%s", result.LCS);
}

我的答案

#include<stdio.h>
#include<string.h>
int flag[50][50]={0};
int dp[50][50]={0};
struct Result res;
void PrintLCS(int i,int j,int k,char s1[],char s2[])
{
    if(i==0||j==0)
        return ;
    if(flag[i][j]==0)
    {
            k++;    
        PrintLCS(i-1,j-1,k,s1,s2);
            printf("%c",s1[i-1]);  
    }
    else if(flag[i][j]==1)
        PrintLCS(i-1,j,k,s1,s2);
    else
        PrintLCS(i,j-1,k,s1,s2);
}

struct Result LCS(char s1[],char s2[])
{
    for(int i=1;i<=strlen(s1);i++)
    {
        for(int j=1;j<=strlen(s2);j++)
        {
            if(s1[i-1]==s2[j-1]){    
                        dp[i][j]=dp[i-1][j-1]+1;
                        flag[i][j]=0;}
            else if(dp[i-1][j]>=dp[i][j-1]){
                dp[i][j]=dp[i-1][j];
                        flag[i][j]=1;}
            else{
                dp[i][j]=dp[i][j-1];
                        flag[i][j]=-1;}
        }
    }

    int k=0;
    PrintLCS(strlen(s1),strlen(s2),k,s1,s2);
    return res;
}