子序列与子串问题

1. 序列与字符串：基本概念

在计算机科学中，一个序列 (Sequence) 是一个有序的元素集合。这些元素可以是数字、字符或任何其他数据类型。例如，数组 [10, 20, 5, 30] 就是一个整数序列。

字符串 (String) 是一种特殊的序列，它的元素是字符。例如，"hello" 就是一个由字符 'h', 'e', 'l', 'l', 'o' 组成的字符串。在 C++ 中，我们通常使用 std::string 类型或字符数组 char[] 来表示字符串。

对于一个长度为 nn 的字符串 SS，我们可以用 S[i]S[i] 来表示其第 ii 个字符，其中索引通常从 00 开始，即 S,S,…,S[n−1]S, S, \dots, S[n-1]。

2. 子串 (Substring)

2.1. 定义

一个字符串 TT 如果是另一个字符串 SS 的子串，那么 TT 必须是 SS 中连续的一部分。

换句话说，如果字符串 SS 的长度为 nn，那么它的任何子串都可以表示为 S[i…j]S[i \dots j]，即从索引 ii 开始到索引 jj 结束的所有字符组成的连续段，其中 0≤i≤j<n0 \le i \le j < n。

示例： 对于字符串 S="banana"S = \text{"banana"}：

  • "ban" 是一个子串。(S[0…2]S[0 \dots 2])
  • "nan" 是一个子串。(S[2…4]S[2 \dots 4])
  • "a" 是一个子串。
  • "banana" 本身也是一个子串。
  • "bna" 不是子串，因为字符 'b', 'n', 'a' 在原字符串中不是连续的。
  • 空字符串 "" 被认为是任何字符串的子串。

2.2. 子串的数量

一个长度为 nn 的非空字符串，它有多少个不同的非空子串？

我们可以通过枚举子串的起始位置和结束位置来计算。

  • 起始位置 ii 可以从 00 到 n−1n-1。
  • 对于每个起始位置 ii，结束位置 jj 可以从 ii 到 n−1n-1。

总的子串数量（包括重复的）是所有可能的 (i,j)(i, j) 组合数，即：

$$\sum_{i=0}^{n-1} (n-i) = n + (n-1) + \dots + 1 = \frac{n(n+1)}{2} $$

这是所有子串的总数。例如，对于 "aba"，子串有 "a", "ab", "aba", "b", "ba", "a"。总共 6 个，符合 3(3+1)2=6\frac{3(3+1)}{2} = 6。

如果问题是不同的非空子串数量，就需要去重。对于 "aba"，不同的子串是 "a", "b", "ab", "ba", "aba"，共 5 个。计算不同子串的数量通常需要更复杂的算法（如后缀自动机或后缀树），超出了基础笔试的范围，但理解总数的计算是必要的。

2.3. 经典问题：最长公共子串 (Longest Common Substring)

最长公共子串问题是寻找两个或多个字符串中，长度最长的共同子串。

题意概括：给定两个字符串 S1S_1 和 S2S_2，找出它们的最长公共子串的长度。

解法：动态规划 (Dynamic Programming)

我们可以使用一个二维数组 dpdp 来解决这个问题。dp[i][j]dp[i][j] 表示以 S1S_1 的第 ii 个字符 (S1[i−1]S_1[i-1]) 和 S2S_2 的第 jj 个字符 (S2[j−1]S_2[j-1]) 结尾的最长公共子串的长度。

状态转移方程：

  • 如果 S1[i−1]==S2[j−1]S_1[i-1] == S_2[j-1]，说明这两个字符可以延续之前的公共子串。所以，以它们结尾的公共子串长度，等于以它们前一个字符结尾的公共子串长度加 1。dp[i][j]=dp[i−1][j−1]+1dp[i][j] = dp[i-1][j-1] + 1
  • 如果 S1[i−1]≠S2[j−1]S_1[i-1] \neq S_2[j-1]，那么以这两个字符结尾的公共子串不存在，因为子串必须是连续的。所以长度为 0。dp[i][j]=0dp[i][j] = 0

在整个计算过程中，我们需要一个变量来记录所有 dp[i][j]dp[i][j] 的最大值，这个最大值就是最终的答案。

C++ 代码示例

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    string s1, s2;
    cin >> s1 >> s2;

    int n = s1.length();
    int m = s2.length();
    
    // dp[i][j]: 以 s1[i-1] 和 s2[j-1] 结尾的最长公共子串长度
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    int ans = 0;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = 0;
            }
            // 记录所有dp值的最大值
            ans = max(ans, dp[i][j]);
        }
    }

    cout << ans << endl;

    return 0;
}

// 复杂度分析:
// 时间复杂度: O(n * m)，因为我们填充了一个 n*m 大小的二维数组。
// 空间复杂度: O(n * m)，用于存储dp表。
// (空间可以优化到 O(min(n, m))，但这里为了清晰展示逻辑，使用二维数组)

3. 子序列 (Subsequence)

3.1. 定义

一个字符串 TT 如果是另一个字符串 SS 的子序列，那么 TT 是通过从 SS 中删除零个或多个字符，而不改变其余字符的相对顺序得到的。

子序列和子串的关键区别在于：子序列的字符不必连续。

示例： 对于字符串 S="banana"S = \text{"banana"}：

  • "bna" 是一个子序列。可以从 "banana" 中保留第 1、3、6 个字符得到。
  • "bnn" 是一个子序列。可以保留第 1、5、6 个字符。
  • "aa" 是一个子序列。
  • "ban" 同时是子串和子序列。
  • "baan" 不是子序列，因为第二个 'a' 出现在 'n' 的后面，这与原串中的相对顺序不符。
  • 空字符串 "" 被认为是任何字符串的子序列。

3.2. 子序列的数量

一个长度为 nn 的字符串，它有多少个不同的子序列？

对于原字符串中的每个字符，我们都有两种选择：选入子序列，或者不选。由于有 nn 个字符，每个字符都有 2 种独立的选项，根据乘法原理，总共的可能性是：

2n2^n

这个计算包含了空子序列（所有字符都不选的情况）。如果问题要求非空子序列的数量，那么答案是 2n−12^n - 1。

这个公式计算的是所有可能的子序列，可能会有重复。例如，对于 "aba"，子序列有："", "a", "b", "a", "ab", "aa", "ba", "aba"。去重后为 "", "a", "b", "ab", "aa", "ba", "aba"。计算不同子序列的数量是一个更难的动态规划问题。

3.3. 经典问题：最长公共子序列 (Longest Common Subsequence)

最长公共子序列（LCS）是算法竞赛中的一个经典问题。

题意概括：给定两个字符串 S1S_1 和 S2S_2，找出它们的最长公共子序列的长度。

解法：动态规划 (Dynamic Programming)

同样，我们使用一个二维数组 dpdp。dp[i][j]dp[i][j] 的含义是：字符串 S1S_1 的前 ii 个字符 (S1[0…i−1]S_1[0 \dots i-1]) 和 S2S_2 的前 jj 个字符 (S2[0…j−1]S_2[0 \dots j-1]) 的最长公共子序列的长度。

状态转移方程： 我们考虑 S1S_1 的第 ii 个字符 (S1[i−1]S_1[i-1]) 和 S2S_2 的第 jj 个字符 (S2[j−1]S_2[j-1])。

  1. 如果 S1[i−1]==S2[j−1]S_1[i-1] == S_2[j-1]： 这两个字符相等，那么它们可以共同构成公共子序列的一部分。这个公共子序列的长度等于 S1S_1 前 i−1i-1 个字符和 S2S_2 前 j−1j-1 个字符的 LCS 长度加 1。

    dp[i][j]=dp[i−1][j−1]+1dp[i][j] = dp[i-1][j-1] + 1

  2. 如果 S1[i−1]≠S2[j−1]S_1[i-1] \neq S_2[j-1]： 这两个字符不相等，那么它们不能同时作为 LCS 的结尾。LCS 只能来自于以下两种情况之一，我们取其中的较大者：

    • S1S_1 的前 i−1i-1 个字符与 S2S_2 的前 jj 个字符的 LCS。 (相当于忽略 S1[i−1]S_1[i-1])
    • S1S_1 的前 ii 个字符与 S2S_2 的前 j−1j-1 个字符的 LCS。 (相当于忽略 S2[j−1]S_2[j-1])
    dp[i][j]=max⁡(dp[i−1][j],dp[i][j−1])dp[i][j] = \max(dp[i-1][j], dp[i][j-1])

最终的答案就是 dp[n][m]dp[n][m]，其中 nn 和 mm 分别是 S1S_1 和 S2S_2 的长度。

C++ 代码示例

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    string s1, s2;
    cin >> s1 >> s2;

    int n = s1.length();
    int m = s2.length();
    
    // dp[i][j]: s1的前i个字符和s2的前j个字符的LCS长度
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    cout << dp[n][m] << endl;

    return 0;
}

// 复杂度分析:
// 时间复杂度: O(n * m)，因为我们填充了一个 n*m 大小的二维数组。
// 空间复杂度: O(n * m)，用于存储dp表。
// (空间同样可以优化到 O(min(n, m)))

4. 题型解析

在笔试中，关于子串和子序列的题目通常以选择、判断、阅读程序和填空等形式出现。

4.1. 选择与判断题

这类题目主要考察对基本定义的理解。

例题 1 (判断题)：

字符串 "ace" 是字符串 "abcde" 的一个子串。

分析：错误。子串必须是连续的。"ace" 在 "abcde" 中不是连续的。它是 "abcde" 的一个子序列。

例题 2 (选择题)：

对于字符串 S="abacaba"S = \text{"abacaba"}，以下哪个是它的子序列但不是子串？ A. "aba" B. "aca" C. "baca" D. "ca"

分析：

  • A. "aba"：是子串（从索引0开始）。
  • B. "aca"：是子串（从索引2开始）。
  • C. "baca"：是子串（从索引1开始）。
  • D. "ca"：在原串中找不到连续的 "ca"。但可以取第3个字符 'c' 和第5个字符 'a' 组成，保持了相对顺序，所以是子序列。 答案：D

例题 3 (选择题)：

一个长度为 5 的字符串 s，最多有多少个非空子串？ A. 5 B. 15 C. 25 D. 31

分析： 题目问的是“子串”的数量。套用公式 n(n+1)2\frac{n(n+1)}{2}，其中 n=5n=5。

5(5+1)2=302=15\frac{5(5+1)}{2} = \frac{30}{2} = 15

这个公式计算的是所有子串（包括重复的）的数量。题目中的“最多”一词暗示了字符串中的字符各不相同，此时所有子串也都是不同的。 注意选项 D 的 31 是 25−12^5-1，这是非空“子序列”的数量。 答案：B

4.2. 程序阅读题

程序阅读题通常会给出一个实现子串或子序列相关算法的代码片段，要求你分析其功能或输出。

例题 4 (程序阅读)：

阅读以下 C++ 代码，输入为 s1 = "abcf" 和 s2 = "acbf"，请问输出是什么？

#include<bits/stdc++.h>
using namespace std;
int main() {
 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 string s1, s2;
 cin >> s1 >> s2;
 int n = s1.length(), m = s2.length();
 vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
 for (int i = 1; i <= n; ++i) {
     for (int j = 1; j <= m; ++j) {
         if (s1[i - 1] == s2[j - 1]) {
             dp[i][j] = dp[i - 1][j - 1] + 1;
         } else {
             dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
         }
     }
 }
 cout << dp[n][m] << endl;
 return 0;
}

分析： 这段代码是典型的计算最长公共子序列（LCS）的模板。我们要找出 "abcf" 和 "acbf" 的 LCS。 手动模拟 DP 表的计算过程：

  • S1S_1: a b c f
  • S2S_2: a c b f

LCS 可能是：

  • "abf" (长度3)
  • "acf" (长度3)

我们来追踪几个关键的 DP 值：

  • dp 表大小为 5x5。
  • dp[1][1] ('a' vs 'a'): dp+1=1dp + 1 = 1
  • dp[2][2] ('b' vs 'c'): max⁡(dp,dp)=max⁡(1,1)=1\max(dp, dp) = \max(1, 1) = 1
  • dp[2][3] ('b' vs 'b'): dp+1=1+1=2dp + 1 = 1+1=2. ("ab" vs "acb")
  • dp[3][2] ('c' vs 'c'): dp+1=1+1=2dp + 1 = 1+1=2. ("abc" vs "ac")
  • ...
  • 最终 dp[4][4] (比较 'f' 和 'f')：此时 s1[3] == s2[3]。所以 dp[4][4] = dp[3][3] + 1。 而 dp[3][3] 是 "abc" 和 "acb" 的 LCS 长度。我们看到 "ab" 和 "ac" 都是长度为 2 的公共子序列。所以 dp[3][3]=2。 因此 dp[4][4] = 2 + 1 = 3。

输出：3

4.3. 程序填空题

这类题目会给出一个不完整的代码，要求你补全关键部分，通常是动态规划的状态转移方程。

例题 5 (程序填空)：

下面的代码用于计算字符串 s1 和 s2 的最长公共子串的长度。请补全 // TODO 部分。

#include<bits/stdc++.h>
using namespace std;
int main() {
 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 string s1, s2;
 cin >> s1 >> s2;
 int n = s1.length(), m = s2.length();
 vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
 int ans = 0;
 for (int i = 1; i <= n; ++i) {
     for (int j = 1; j <= m; ++j) {
         if (s1[i - 1] == s2[j - 1]) {
             // TODO
         } else {
             dp[i][j] = 0;
         }
         ans = max(ans, dp[i][j]);
     }
 }
 cout << ans << endl;
 return 0;
}

分析： 该代码的框架是计算最长公共子串。回顾其 DP 定义：dp[i][j]dp[i][j] 是以 S1[i−1]S_1[i-1] 和 S2[j−1]S_2[j-1] 结尾的公共子串长度。当这两个字符相等时，它可以延续前一个位置的公共子串。所以，长度是在 dp[i−1][j−1]dp[i-1][j-1] 的基础上加 1。

填空内容：dp[i][j] = dp[i-1][j-1] + 1;

5. 拓展与关联

5.1. 编辑距离 (Edit Distance)

编辑距离是另一个与 LCS 密切相关的经典问题。它衡量的是将一个字符串 S1S_1 转换为另一个字符串 S2S_2 所需的最少单字符编辑（插入、删除、替换）次数。

编辑距离的 DP 解法与 LCS 非常相似。令 dp[i][j]dp[i][j] 为 S1S_1 的前 ii 个字符变为 S2S_2 的前 jj 个字符所需的最少操作次数。

  • 如果 S1[i−1]==S2[j−1]S_1[i-1] == S_2[j-1]，无需操作，dp[i][j]=dp[i−1][j−1]dp[i][j] = dp[i-1][j-1]。
  • 如果 S1[i−1]≠S2[j−1]S_1[i-1] \neq S_2[j-1]，可以有三种操作：
    1. 替换：将 S1[i−1]S_1[i-1] 替换为 S2[j−1]S_2[j-1]。代价是 dp[i−1][j−1]+1dp[i-1][j-1] + 1。
    2. 删除：删除 S1[i−1]S_1[i-1]。代价是 dp[i−1][j]+1dp[i-1][j] + 1。
    3. 插入：在 S1S_1 后插入一个字符（等价于从 S2S_2 中删除 S2[j−1]S_2[j-1]）。代价是 dp[i][j−1]+1dp[i][j-1] + 1。 取三者中的最小值：
    $$dp[i][j] = 1 + \min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) $$理解 LCS 有助于快速掌握编辑距离问题。

5.2. 回文子串/子序列

回文是指正读反读都一样的字符串，如 "level" 或 "madam"。

  • 最长回文子串：可以在 O(n2)O(n^2) 时间内用 DP 解决，也可以用更高级的 Manacher 算法在 O(n)O(n) 时间内解决。
  • 最长回文子序列：这个问题可以转化为 LCS 问题。一个字符串 SS 的最长回文子序列，就是 SS 和其反转字符串 SrevS_{rev} 的最长公共子序列。例如，对于 S="google"S = \text{"google"}，其反转 Srev="elgoog"S_{rev} = \text{"elgoog"}。LCS("google","elgoog")LCS(\text{"google"}, \text{"elgoog"}) 是 "goog"，长度为 4。

6. 总结

特性 子串 (Substring) 子序列 (Subsequence)
定义 原始字符串中连续的字符片段 从原始字符串中按原相对顺序选出的字符序列
连续性 必须连续 不必连续
示例 ("abcde") "bcd" 是 "ace" 是
数量 (长度为 n) 总数为 n(n+1)2\frac{n(n+1)}{2} 总数为 2n2^n (含空)
LCS DP 转移 (不等时) dp[i][j]=0dp[i][j] = 0 dp[i][j]=max⁡(dp[i−1][j],dp[i][j−1])dp[i][j] = \max(dp[i-1][j], dp[i][j-1])
  1. 评测队列
  2. 服务状态
  3. 兼容模式
  4. 主题
  2. 陕ICP备2025061476号
  3. Worker 0, 132ms
  4. Powered Dong Dong