最长公共子序列 参考

习题一：最长公共子序列的长

• 思路：考察简单动态规划
• 略

Description

求两个序列的最每组测试样例都为一行，两组字符串，每组不超过1000，用空格隔开。求最长公共子序列，都为小写字母。

Input

每组测试样例都为一行，两组字符串，每组不超过1000，用空格隔开。

Output

对于每个测试实例，输出最长公共子序列的长度，每个实例的输出占一行。

Sample

• Input

abcfbc abfcab
programming contest 
abcd mnp

• Output

4
2
0

• Code:

#include <iostream>
#include <cstring>
#include <algorithm>
// #define LOCAL
using namespace std;

const int N = 1e3 + 10;
char a[N], b[N];
int dp[N][N], len_a, len_b;

void lcs(int len1, int len2)
{
    for (int i = 1; i <= len1; i++)
    {
        for (int j = 1; j <= len2; j++)
        {
            if (a[i - 1] == b[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else if (dp[i - 1][j] > dp[i][j - 1])
                dp[i][j] = dp[i - 1][j];
            else
            {
                dp[i][j] = dp[i][j - 1];
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
#ifdef LOCAL
    freopen("1028_15.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    while (~scanf("%s %s", a, b))
    {
        // memset(dp, 0, sizeof(dp));
        len_a = strlen(a), len_b = strlen(b);
        // cout << "a:";
        // for (int i = 0; i < len_a; i++)
        //     cout << a[i];
        // cout << endl
        //      << "b:";
        // for (int i = 0; i < len_b; i++)
        //     cout << b[i];
        // cout << endl;
        lcs(len_a, len_b);
        printf("%d\n", dp[len_a][len_b]);
    }
    return 0;
}

习题二：最长公共子序列的字符串

• 思路：考察简单动态规划
• 略

Description

给出两个字符串A B，求A与B的最长公共子序列（子序列不要求是连续的）。

比如两个串为：abcicba 和 abdkscab，则 ab是两个串的子序列，abc也是，abca也是，其中abca是这两个字符串最长的子序列。

Input

第1行：字符串A
第2行：字符串B
(A,B的长度 <= 1000)

Output

输出最长的子序列，如果有多个，随意输出1个。

Sample

• Input

abcicba
abdkscab

• Output

abca // abcb?

• Code:

#include <iostream>
#include <cstring>
#include <algorithm>
// #define LOCAL
#define INF 0x3f3f3f3f
using namespace std;

const int N = 1e3 + 10;
char a[N], b[N];
int dp[N][N], len_a, len_b;

void lcs(int len_a, int len_b)
{
    for (int i = 1; i <= len_a; i++)
    {
        for (int j = 1; j <= len_b; j++)
        {
            if (a[i - 1] == b[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else if (dp[i - 1][j] > dp[i][j - 1])
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = dp[i][j - 1];
        }
    }
}

void llcs()
{
    int i, j, z = 0;
    char c[1001];
    memset(c, 0, sizeof(c));
    i = len_a, j = len_b;
    while (i != 0 && j != 0)
    {
        if (a[i - 1] == b[j - 1])
        {
            c[z++] = a[--i];
            j--;
        }
        else if (dp[i - 1][j] < dp[i][j - 1])
            j--;
        else if (dp[i][j - 1] <= dp[i - 1][j])
            i--;
    }
    for (i = z - 1; i >= 0; i--)
        printf("%c", c[i]);
    printf("\n");
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
#ifdef LOCAL
    freopen("1028_15.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    while (~scanf(" %s", a))
    {
        scanf(" %s", b);
        memset(dp, 0, sizeof(dp));
        len_a = strlen(a), len_b = strlen(b);
        lcs(len_a, len_b);
        llcs();
    }
    return 0;
}