CSP-S 2019 第一轮 第33题：若tlen=10，输出为 2，则 slen 最小为（）

题目

$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+1$ 个字符构成的字符串，若 $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; ++i){
        while(j <= slen && tmp >= suf[j] + 1) ++j;
        ans = max(ans, j - i - 1);
        tmp = pre[i];
    }
    cout << ans << endl;
    return 0;
}

提示：

- $t[0\dots pre[i]-1]$ 是 $s[0\dots i]$ 的子序列；
- $t[suf[i]+1\dots tlen-1]$ 是 $ s[i\dots slen-1]$ 的子序列。

若 tlen=10，输出为 $2$，则 $slen$ 最小为（）。

选项

• A. 0
• B. 10
• C. 12
• D. 1

答案

C

题解

答案是 C．12。

这段程序求的是：从 \(s\) 中删除一段连续的字符，使 \(t\) 仍然是剩余字符串的子序列，最多能删除多少个字符。

看最后一个循环，在处理位置 i 时：

• tmp 表示左侧 \(s[0..i-1]\) 最多能匹配 \(t\) 的多少个开头字符。
• suf[j] + 1 表示保留右侧 \(s[j..slen-1]\) 后，还需要左侧匹配多少个开头字符。

因此，当 ``cpp tmp >= suf[j] + 1 `` 时，说明删掉中间的 \(s[i..j-1]\) 后，两侧仍能拼出子序列 \(t\)。

while 结束时，j 已经比最后一个可行位置多了 \(1\)，所以删除长度记为 j - i - 1。

输出为 \(2\)，说明可以删除两个字符，剩下的字符仍能包含长度为 \(10\) 的子序列 \(t\)，于是 \[ slen-2\ge 10\quad\Longrightarrow\quad slen\ge 12. \]

而 \(slen=12\) 确实可以做到。例如： ``text s = aaaaaaaaaaaa （12 个 a） t = aaaaaaaaaa （10 个 a） ` 最多能删除连续的 \(2\) 个 a`，输出恰好为 \(2\)。所以最小值是 12。