CSP-S 提高级 · CSP 2019 提高级第一轮 第 18 题

3.

$t$ 是 $s$ 的子序列的意思是：从 $s$ 中删去若干个字符，可以得到 $t$；特别的，如果 $s=t$，那么 $t$ 也是 $s$ 的子序列；空串是任何串的子序列。例如：$\texttt{acd}$ 是 $\texttt{abcde}$ 的子序列，$\texttt{acd}$ 是 $\texttt{acd}$ 的子序列，但 $\texttt{adc}$ 不是 $\texttt{abcde}$ 的子序列。

$s[x..y]$ 表示 $s[x] \cdots s[y]$ 共 $y-x+l$ 个字符构成的字符串，若 $x>y$ 则 $s[x..y]$ 是空串。$t[x..y]$ 同理。

#include <iostream>
#include <string>
using namespace std;
const int max1 = 202;
string s, t;
int pre[max1], suf[max1];

int main() {
    cin >> s >> t;
    int slen = s.length(), tlen = t.length();

    for (int i = 0, j = 0; i < slen; ++i) {
        if (j < tlen && s[i] == t[j]) ++j;
        pre[i] = j; // t[0..j-1] 是 s[0..i] 的子序列
    }

    for (int  i = slen - 1 , j = tlen - 1; i >= 0; --i) {
        if(j >= 0 && s[i] == t [j]) --j;
        suf[i]= j; // t[j+1..tlen-1] 是 s[i..slen-1] 的子序列
    }

    suf[slen] = tlen -1;
    int ans = 0;
    for (int i = 0, j = 0, tmp = 0; i <= slen

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题考的是'删除一个连续子串后还能否包含t'，核心是把pre和suf数组当成'前缀匹配长度'和'后缀匹配起始位'。拿到题先想：pre[i]表示s[0..i]能匹配t的前缀长度，suf[i]表示s[i..]能匹配t的后缀起始位；然后枚举删除区间的左端点i，用j向右扫找最远右端点，只要pre[i] > suf[j] + 1就说明中间那段删掉后前后还能拼出t，答案就是最大的j-i-1。

最容易栽跟头的是把suf理解反了：代码里suf[i]存的是'未匹配的后缀起始下标'，i越往右suf[i]越大（非递减），很多同学以为它是递减的，导致第1小题直接判错。第2小题当t是s的子序列时输出不一定非零，因为题目求的是'删除一段'，如果s本身已经包含t，最优策略是删除空串，此时j=i，j-i-1=-1，但程序里tmp=pre[i]会在i=slen时取到tlen，循环逻辑会让ans保持0，所以输出0也是合法的，别死磕'非空删除'。第3小题第23行j-i-1可能为负，因为j是while扫出来的右端点，当pre[i]很小而suf[j]很大时j可能停在i左边，一定要代入具体例子验证。第4小题pre[i] > suf[i+1]+1这个条件太苛刻，只要前后能各自拼出t就行，不需要严格大于，很多同学会漏掉'等于'的情况。

这道题考什么

这题考查的是'子序列匹配 + 连续区间删除'的组合模型：给定两个字符串s和t，问从s中删去一段连续子串（可以是空串），剩下的字符按原顺序能否拼出t。程序的目标是求出可以删除的最长连续子串的长度。

关键概念（人话版）

• 子序列：从原串中删掉若干字符，剩下的字符顺序不变。比如"acd"是"abcde"的子序列，但"adc"不是。
• pre[i]：扫描s的前i+1个字符（s[0..i]），能匹配t的前缀长度。也就是说，t[0..pre[i]-1]这一段已经能在s[0..i]里找到。
• suf[i]：从s的第i个字符开始往后扫，能匹配t的后缀起始下标。具体来说，t[suf[i]+1..tlen-1]这一段能在s[i..slen-1]里找到。注意：suf[i]是一个下标，不是长度；而且因为i往右移时可用字符变少，suf[i]是非递减的（越靠右，未匹配的后缀越长，起始下标越大）。
• 删除区间：如果我们决定删掉s[i..j-1]这一段（长度为j-i），那么剩下的就是s[0..i-1]和s[j..slen-1]。要拼出t，必须满足：前缀部分能覆盖t的前pre[i]个字符，后缀部分能覆盖t的剩余字符，且两者不重叠。数学上就是 pre[i] > suf[j] + 1（前缀覆盖的终点严格大于后缀起始点）。