vlambda博客
学习文章列表

Common Subsequence（公共子序列问题）

Description

A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = < x1, x2, ..., xm > another sequence Z = < z1, z2, ..., zk > is a subsequence of X if there exists a strictly increasing sequence < i1, i2, ..., ik > of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = < a, b, f, c > is a subsequence of X = < a, b, c, f, b, c > with index sequence < 1, 2, 4, 6 >. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.

简单说就是Z是X的子序列。给定序列X和Y，求出最长公共子序列的长度。

Input

The program input is from the std input. Each data set in the input contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct.

每行是两个字符串序列。

Output

For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.

输出最长公共子序列的长度。

Sample Input

abcfbc         abfcab 
programming    contest 
abcd           mnp

Sample Output

4 
2
0

LCS算法是一个二维DP，核心思想是：

dp[i][j]表示数列A[1~i]和数列B[1~j]的最长子序列长度。

当A[i]等于A[j]时，dp[i][j] = dp[i-1][j-1]+1，表示增加了一个元素。

如果A[i]和A[j]不相等，则不增加元素，但是要记录dp值，因为后续需要依赖该值，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

实现采用记忆化递归的方式非常自然简单，缺点是性能差，虽然LCS可以采用递推的方式做，而且从dp[0][0]开始递推也比较容易实现，但是注意dp[i][0]都为0，dp[0][j]都为0，采用二维循环，对于数列a和b，每次遍历b都是固定a的一个值，其实是计算表中的一行。理解起来比递归要复杂些，仔细揣摩一下吧！

下图可以帮助理解一下~

源代码：记忆化递归

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <bitset>
#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;

int d[1000][1000];
string s1, s2;

int dp(int i, int j)
{
    if(d[i][j] != -1)
        return d[i][j];

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

    if(s1[i-1] == s2[j-1])
        d[i][j] = dp(i-1, j-1) + 1;
    else
        d[i][j] = std::max(dp(i-1, j), dp(i, j-1));

    return d[i][j];
}

int main()
{
    while(cin>>s1>>s2)
    {
        memset(d, -1, sizeof(d));
        cout << dp(s1.length(), s2.length()) <<endl;
    }

    return 0;
}

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <bitset>
#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;

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

int main() {
    while (cin >> s1 >> s2) {
        int l1 = strlen(s1);
        int l2 = strlen(s2);
        int i, j;

        for (i = 0; i <= l1; i++)
            dp[i][0] = 0;

        for (j = 0; j <= l2; j++)
            dp[0][j] = 0;

        for (i = 1; i <= l1; i++) {
            for (j = 1; j <= l2; j++) {
                if (s1[i - 1] == s2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
        cout << dp[l1][l2] << endl;
    }
    return 0;
}