【算法小总结】LCS问题&&HDU1243

LCS问题，又称最长公共子序列问题，是DP中较简单的一种，今天我们就来简单讲解一下。

设s1:AEGLEGLLELGEL

设s2:LREGELGEGLEG

求两个字符串的最大公共子序列长度

输出：8

dp[i][j]表示匹配到s1的前i个与s2的前j个所得到的最大公共子序列长度。

转移方程：

　　　　dp[i][j]=0 (i==0||j==0)

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

　　　　same(i,j)=(s1[i]==s2[j]?1:0)

来看一道题目（HDU1243）

题意：求两个字符串的最大公共子序列的长度

分析：dp，匹配到时加上字母相同的权值

//公共子序列问题 
//dp[i][j]表示前s1的前i个与s的前j个匹配得到的最大公共子序列 
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,value[200],dp[2005][2005];
char s1[2005],s2[2005];

int main()
{
    while(scanf("%d",&n)!=-1)
    {
        scanf("%s",s1+1);
        for(int i=1;i<=n;++i) scanf("%d",&value[s1[i]]);
        scanf("%s",s1);getchar();
        scanf("%s",s2);
        //memset(dp,0,sizeof(dp));
        int len1=strlen(s1),len2=strlen(s2);
        for(int i=0;i<=len1;++i) dp[i][0]=0;
        for(int i=0;i<=len2;++i) dp[0][i]=0;
        for(int i=0;i<len1;++i)for(int j=0;j<len2;++j)
        {
            dp[i+1][j+1]=max(dp[i][j]+((s1[i]==s2[j])?value[s1[i]]:0),max(dp[i][j+1],dp[i+1][j]));
        }
        printf("%d
",dp[len1][len2]);
    }
}

View Code

如果是输出最大公共子序列呢？

只需再加入一个数组f[i][j]记录匹配的情况

　　　　f[i][j]=0 (s1[i]==s2[j])

　　　　f[i][j]=1 (dp[i][j+1]>dp[i+1][j])

　　　　f[i][j]=2 (dp[i][j+1]<=dp[i+1][j])

还是HDU1243

input

abcd

1 1 1 1

abcabcabc

dacdbdb

output

acbb

//公共子序列问题 
//dp[i][j]表示前s1的前i个与s的前j个匹配得到的最大公共子序列 
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,value[200],dp[2005][2005],f[2005][2005] ;
char s1[2005],s2[2005];

void out(int x,int y)
{
    if(x==0||y==0) return ;
    if(f[x][y]==0)
    {
        out(x-1,y-1);
        printf("%c",s1[x-1]);
    }
    else if(f[x][y]==1) out(x-1,y);
    else out(x,y-1);
}
int main()
{
    while(scanf("%d",&n)!=-1)
    {
        scanf("%s",s1+1);
        for(int i=1;i<=n;++i) scanf("%d",&value[s1[i]]);
        scanf("%s",s1);getchar();
        scanf("%s",s2);
        //memset(dp,0,sizeof(dp));
        int len1=strlen(s1),len2=strlen(s2);
        for(int i=0;i<=len1;++i) dp[i][0]=0;
        for(int i=0;i<=len2;++i) dp[0][i]=0;
        for(int i=0;i<len1;++i)for(int j=0;j<len2;++j)
        {
            if(s1[i]==s2[j]){dp[i+1][j+1]=dp[i][j]+value[s1[i]];f[i+1][j+1]=0;}
            else
            {
                f[i+1][j+1]=((dp[i][j+1]>dp[i+1][j])?1:2);
                dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
            } 
        }
        out(len1,len2);
        puts("");
        printf("%d
",dp[len1][len2]);
    }
}

View Code

最大公共子串问题

这个问题是LCS的变形，较简单

dp[i][j]表示匹配到s1的前i个与s2的前j个所得到的最大公共子串长度。

　　　　dp[i][j]=dp[i-1][j-1]+1 (s1[i]==s2[j])

　　　　dp[i][j]=0 (s1[i]!=s2[j])

如果要输子串就记录最大长度时的位置，然后往回输出即可

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int max_len,dp[1010][1010],t,len1,len2;
char s1[1010],s2[1010];
int main()
{
    for(scanf("%d",&t);t--;)
    {
        scanf("%s%s",s1,s2);
        len1=strlen(s1),len2=strlen(s2);
        max_len=0;
        for(int i=1;i<=len1;++i) dp[i][0]=0;
        for(int i=1;i<=len2;++i) dp[0][i]=0;
        for(int i=1;i<=len1;++i)for(int j=1;j<=len2;++j)
        {
            if(s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=0;
            max_len=max(max_len,dp[i][j]);
        }
        printf("%d
",max_len);
    }
}

View Code