CF1989B Substring and Subsequence 题解

题意简述

给定两个字符串 $a$ 和 $b$（长度均 $\le 100$），求最短的字符串 $s$，使得：

• $a$ 是 $s$ 的子串（连续出现）；
• $b$ 是 $s$ 的子序列（不要求连续，但顺序不变）。

输出 $s$ 的最小长度。

思路分析

设 $n = |a|$，$m = |b|$。

最终构造的 $s$ 必然包含 $a$ 作为连续段。同时，$b$ 的字符按顺序出现在 $s$ 中。我们可以将 $b$ 的字符分为三部分：

1. 在 $a$ 段之前出现的部分（$b$ 的某个前缀）；
2. 在 $a$ 段内部作为子序列匹配的部分（$b$ 的一段连续子串）；
3. 在 $a$ 段之后出现的部分（$b$ 的某个后缀）。

要使 $s$ 最短，我们应尽可能多地利用 $a$ 内部的字符去覆盖 $b$ 的字符，从而减少需要额外放在 $a$ 前后的字符数量。

具体地，假设我们能从 $a$ 中找到 $b$ 的一个连续子段 $b[i..r-1]$ 作为子序列（即存在 $a$ 的一些位置，顺序等于 $b[i..r-1]$），那么可以这样构造 $s$：

这样 $s$ 的长度为：

令 $len = r - i$ 表示 $b$ 的这段连续子串的长度，那么 $|s| = n + m - len$。

因此，问题转化为：最大化 $len$，即 $b$ 中能作为 $a$ 的子序列的最长连续子串的长度。

算法实现

我们可以枚举 $b$ 的每一个起始位置 $i$（$1 \le i \le m$），然后用贪心的方式匹配 $a$：从 $a$ 的第一个字符开始扫描，每当遇到与 $b$ 当前所需字符相同时，就将 $b$ 的指针右移。这样能匹配到的最大长度就是从 $i$ 开始能匹配的最长连续段。

具体过程：

• 外层循环枚举 $i$ 作为 $b$ 的起始位置。
• 内层两个指针 $l$（遍历 $a$）和 $r$（初始 $=i$，表示 $b$ 中当前待匹配位置）：
  • 若 $a[l] = b[r]$，则 $r$ 右移（匹配成功）；
  • $l$ 始终右移（扫描 $a$）。
• 当 $l$ 超过 $n$ 或 $r$ 超过 $m$ 时停止，记录 $len = r - i$。

对所有 $i$ 取最大的 $len$，答案即为 $n + m - \max(len)$。

时间复杂度：对于每组测试数据，外层 $O(m)$，内层 $O(n)$，总计 $O(nm)$。$t \le 10^3$，$n,m \le 100$，总计算量约 $10^7$，可以轻松通过。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    int T;
    cin >> T;
    while (T--) {
        string a, b;
        cin >> a >> b;
        int n = a.size(), m = b.size();
        // 在前面插入一个占位符，使得下标从 1 开始
        a = ' ' + a;
        b = ' ' + b;
        
        int max_len = 0;
        for (int i = 1; i <= m; ++i) {
            int l = 1, r = i;          // l 扫描 a，r 扫描 b
            while (l <= n && r <= m) {
                if (a[l] == b[r]) ++r; // 匹配成功，b 指针右移
                ++l;                   // a 指针始终右移
            }
            max_len = max(max_len, r - i);
        }
        cout << n + m - max_len << '\n';
    }
    return 0;
}