LCS最长公共子序列

http://poj.org/problem?id=1458

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int MAXN=1000;

char sz1[MAXN];

char sz2[MAXN];

int dp[MAXN+10][MAXN+10];

/*

最后一个字符相同

dp[i][j]=dp[i-1][j-1]+1;

最后一个字符不同：

dp[i][j]=max(dp[i-1][j], dp[i][j-1]);

dp[i][0]=0;

dp[0][j]=0;

*/

int main()

{

    while(scanf("%s%s", sz1+1, sz2+1)==2)

    {

        int len1=strlen(sz1+1);

        int len2=strlen(sz2+1);

        for(int i=1;i<=len1;i++)

            for(int j=1;j<=len2;j++)

            {

                if(sz1[i]==sz2[j])

                    dp[i][j]=dp[i-1][j-1]+1;

                else

                    dp[i][j]=max(dp[i-1][j], dp[i][j-1]);

            }

        printf("%d
",dp[len1][len2]);

    }

    return 0;

}

改进一下，增加公共字符串打印：就是增加一个c数组用来记录选择的方向

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int MAXN=1000;

char sz1[MAXN];

char sz2[MAXN];

int dp[MAXN+10][MAXN+10];

char c[MAXN+10][MAXN+10];

/*

 *

dp[i][0]=0;

dp[0][j]=0;

最后一个字符相同

dp[i][j]=dp[i-1][j-1]+1;

最后一个字符不同：

dp[i][j]=max(dp[i-1][j], dp[i][j-1]);

*/

void print_lcs(int i, int j)

{

    if(i==0 || j==0) return;

    if(c[i][j]=='d')

    {

        print_lcs(i-1, j-1);

        printf("%c", sz1[i]);

    }

    else if(c[i][j]=='u')

        print_lcs(i-1, j);

    else

        print_lcs(i, j-1);

}

int main()

{

    while(scanf("%s%s", sz1+1, sz2+1)==2)//第0个字符空着，从1开始存

    {

        int len1=strlen(sz1+1);

        int len2=strlen(sz2+1);

        for(int i=0;i<=len1;i++)

            dp[i][0]=0;

        for(int j=0;j<=len2;j++)

            dp[0][j]=0;

        for(int i=1;i<=len1;i++)

            for(int j=1;j<=len2;j++)

            {

                if(sz1[i]==sz2[j])

                {

                    dp[i][j]=dp[i-1][j-1]+1;

                    c[i][j]='d';//斜对角

                }

                else

                {

                    if(dp[i-1][j]>dp[i][j-1])

                    {

                       dp[i][j]=dp[i-1][j];

                       c[i][j]='u';//上

                    }

                    else

                    {

                        dp[i][j]=dp[i][j-1];

                        c[i][j]='l';//左

                    }

                }

            }

        printf("%d
",dp[len1][len2]);

        print_lcs(len1, len2);

        printf("
");

    }

    return 0;

}

参考

程序设计导引及在线实践

计算机算法设计与分析（第2版）_王晓东

计算机算法设计与分析+王晓东+(第3版)