C3-F 最长公共子串和最长公共子序列

题目描述

给定两个仅包含小写英文字母的字符串 S1S_1，S2S_2，试求二者最长公共子串的长度，以及二者最长公共子序列的长度。

我们称 AA 是 SS 的子串，当且仅当 A 可由 S 删去一段前缀与一段后缀得到，例如 dest 和 star 都是 jadestar 的子串，而 jar 不是。

我们称 AA 是 SS 的子序列，当且仅当 A 可由 S 删去一些字符得到，例如 jet 和 jar 都是 jadestar 的子序列，而 rest 不是。

我们称 AA 是 S1S_1 与 S2S_2 的公共子串，当且仅当 AA 既是 S1S_1 的子串又是 S2S_2 的子串。

我们称 AA 是 S1S_1 与 S2S_2 的公共子序列，当且仅当 AA 既是 S1S_1 的子序列又是 S2S_2 的子序列。

输入

本题测试点包含多组数据。

第一行，一个正整数 T（1≤T≤10）T（1≤T≤10），表示数据组数。

对于每组数据：

第一行，一个字符串 S1（1≤∣S1∣≤2000）S_1（1≤|S_1|≤2000）。

第二行，一个字符串 S2（1≤∣S2∣≤2000）S_2（1≤|S_2|≤2000）。

输出

对于每组数据：

输出一行，两个整数，分别为 S1S_1 与 S2S_2 最长公共子串的长度，以及最长公共子序列的长度。

题目分析

求最长公共子串

可以先求出子串以每个位置结尾时的答案，最后取最大值。dp[i][j]dp[i][j]表示S1S_1的前ii个字符与S2S_2的前jj个字符中最长公共子串，如果S1[i]==S2[j]S_1[i]==S_2[j]，则以该字符结尾的答案等效于：S1S_1的前i−1i-1个字符与S2S_2的前j−1j-1个字符比较的结果+1；不相等则等效于：匹配中断，此时结果应清零。由此可得状态转移方程：

dp[i][j]=dp[i−1][j−1]+1S1[i]==S2[j]dp[i][j]=0S1[i]≠S2[j]dp[i][j]=dp[i-1][j-1]+1\qquad S_1[i]==S_2[j] \\dp[i][j]=0 \qquad S_1[i]\not=S_2[j]

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int MaxLengthPublicString(char *s1, char *s2)
{
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int maxLength = 0;
    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] + 1;
                if (dp[i + 1][j + 1] > maxLength)
                {
                    maxLength = dp[i + 1][j + 1];
                }
            }
            else
            {
                dp[i + 1][j + 1] = 0;
            }
        }
    }
    return maxLength;
}

求最长公共子序列

可以先求两个字符串子串的最长公共子序列，dp[i][j]dp[i][j]表示S1S_1的前ii个字符与S2S_2的前jj个字符中最长公共子序列。如果S1[i]==S2[j]S_1[i]==S_2[j]，则以该字符结尾的答案等效于：S1S_1的前i−1i-1个字符与S2S_2的前j−1j-1个字符最长公共子序列长度+1；不等于则选择舍去其中一个字符，留下一个作为下一个待匹配的字符，即为max(dp[i][j−1],dp[i−1][j])max(dp[i][j-1],dp[i-1][j])。

dp[i][j]=dp[i−1][j−1]+1S1[i]==S2[j]dp[i][j]=max(dp[i][j−1],dp[i−1][j])S1[i]≠S2[j]dp[i][j]=dp[i-1][j-1]+1\qquad S_1[i]==S_2[j] \\dp[i][j]=max(dp[i][j-1],dp[i-1][j]) \qquad S_1[i]\not=S_2[j]

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int MaxLengthPublicXuLie(char *s1, char *s2)
{
    int len1 = strlen(s1);
    int 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 = 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] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];
            }
        }
    }

    return dp[len1][len2];
}