27 动态规划DP--最长公共子序列LCS

理论说明

有两个字符串S1和S2,求一个最长的公共子串，即求字符串S3,它同时为S1和S2的子串，且要求它的长度最长，并确定这个长度。这个问题被我们称为最长公共子序列问题。

与求最长递增子序列一样，我们首先将问题分割成一些子问题，我们用dp[i][j]表示S1中前i个字符与S2中前j个字符分别组成的两个前缀字符串的最长公共子串长度。显然的，当i、j较小时我们可以直接得到答案，如dp[0][j]必等于0.那么，假设我们已经求得dp[i][j]（0<=i<x，0<=j<y）的所有值，考虑如何由这些值继续推得dp[x][y],求得S1前x个字符组成的前缀子串和S2前y个字符组成的前缀子串的最长公共子序列长度。若S1[x]==S2[y]，即S1中的第x个字符和S2中的第y个字符相同，同时由于他们都是各自前缀子串的最后一个字符，那么必然存在一个最长公共子串以S1[x]或S2[y]结尾，其他部分等价于S1中的前x-1和字符和S2中的前y-1个字符的最长公共子串。所以这个子串的长度比dp[x-1][y-1]又增加1，即dp[x][y]=dp[x-1][y-1]+1。相反的，若S1[x]！=S2[y],那么此时其最长公共子串长度为S1中的前x-1个字符和S2中前y个字符的最长公共子串长度与S1中前x个字符和S2中前y-1个字符的最长公共子串长度的较大者，即在这两种情况下得到的最长公共子串都不会因为其中一个字符串又增加了一个字符长度而发生改变。即dp[x][y]=max(dp[x-1][y],dp[x][y-1]。

假设有两个字符串S1和S2,其中S1的长度为n,S2的长度为m,用dp[i][j]表示S1前i个字符组成的前缀子串与S2前j个字符组成的前缀子串的最长公共子串长度，那么：

dp[0][j]=0  (0<=j<=m)
  
dp[i][0]=0  (0<=i<=n)
  
dp[i][j]=dp[i-1][j-1]+1  (S1[i]==S2[j])
  
dp[i][j]=max(dp[i-1][j],dp[i][j-1])  (S1[i]!=S2[j])

题目来源

2008年上海交通大学计算机研究生机试真题

题目描述

Find a longest common subsequence of two strings.

输入说明

First and second line of each input case contain two strings of lowercase character a…z. There are no spaces before, inside or after the strings. Lengths of strings do not exceed 100

输出说明

For each case, output k – the length of a longest common subsequence in one line.

样例展示

输入：
abcd
cxbydz
复制
输出：
2

C++代码

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

int dp[101][101];
char s1[101];
char s2[101];

int max(int a,int b) {
    return a>b ? a:b;
}

int main(){
    while(scanf("%s%s",s1,s2)!=EOF) {
        int l1=strlen(s1);
        int l2=strlen(s2);
        
        for(int i=0;i<=l1;i++) dp[i][0]=0;
        for(int j=0;j<=l2;j++) dp[0][j]=0;
        
        for(int i=1;i<=l1;i++) {
            for(int j=1;j<=l2;j++) {
                if(s1[i-1]!=s2[j-1]) {
                    dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
                }
                else dp[i][j]=dp[i-1][j-1]+1;
            }
        }
        printf("%d\n",dp[l1][l2]);
    }
    return 0;
}

这里没啥好说的，想起来之前读CLRS时，还能输出最长LCS字符串的值，找了一下之前写的代码，也贴这里了。

/*****************************************
 * 作者: Zanejins
 * 日期: 2022-03-31
 * 功能：完成最长子序列
 * ***************************************/
#include<iostream>
using namespace std;

const int N=80;
int b[N][N]; //b[i][j]表示c[i][j]所选择的问题的最优解
             //0表示邪，1表示上，2表示左
int c[N][N]; //c[i][j]表示X的前i个组成的字符串和Y的前j个组成的字符串的LCS
             //其大小应该是[0...X.size][0...Y.size]

void lcs(string x,string y) {
    int m=x.size();
    int n=y.size();
    for(int i=0;i<=m;i++) {  //X的前i个和Y的0个构成的LCS必然是0
        c[i][0]=0;            
    }
    for(int j=0;j<=n;j++) {  //Y的前j个和X的0个构成的LCS必然是0
        c[0][j]=0;
    }
    for(int i=1;i<=m;i++) {
        for(int j=1;j<=n;j++) {
            if(x[i-1]==y[j-1]) {
                c[i][j]=c[i-1][j-1]+1;
                b[i][j]=0; //表示邪
            }
            else if(c[i-1][j]>=c[i][j-1]) {
                c[i][j]=c[i-1][j];
                b[i][j]=1; //表示上
            }
            else {
                c[i][j]=c[i][j-1];
                b[i][j]=2;//表示左
            }
        }
    }
}
void print(string x,int i,int j) {
    if(i==0 || j==0) return;
    if(b[i][j]==0) {  //表示邪
        print(x,i-1,j-1);
        printf("%c",x[i-1]);
        
    }
    else if(b[i][j]==1) { //表示上
        print(x,i-1,j);
    }
    else {
        print(x,i,j-1); //表示左
    }
}
int main() {
    string x,y;
    printf("Please input X:");cin>>x;
    printf("Please input Y:");cin>>y;
    int m=x.size();
    int n=y.size();
    lcs(x,y);
    print(x,m,n);
}