题解

题面描述

给定两个字符串 $s$（长度 $n$）和 $t$（长度 $m$），为了数据安全，需要删除 $s$ 中的字符，使得 $t$ 不再作为 $s$ 的子串（即连续片段）出现。删除顺序由长度为 $n$ 的排列 $a$ 给出，表示第 $i$ 次删除位置为 $a_i$（删除后用空白字符替代，不会合并剩余字符）。

请问最少需要删除多少个字符，才能保证删除后的 $s$ 中不包含 $t$ 作为子串？

思路

1. 二分答案：设尝试删除前 $k$ 次（位置 $a_1, \dots, a_k$），检查此时剩余的 $s$ 是否包含 $t$ 作为子串。
2. 判断子串：维护布尔数组 $\mathrm{del}[1\dots n]$，标记被删除的位置。然后对每个可能的子串起始位置 $i$（$1\le i\le n-m+1$）执行：
   1. 若 $\mathrm{del}[i+j]=\mathrm{false}$ 且 $s[i+j]=t[j+1]$ 对所有 $0\le j<m$ 均成立，则存在子串。
   2. 否则继续下一个 $i$。
3. 若任意 $i$ 满足上述条件，则说明目前 $s$ 仍包含 $t$，需要增大 $k$；否则可尝试更小的 $k$。
4. 在区间 $[0,n]$ 上二分，找最小的 $k$ 使得“删除前 $k$ 次后 $s$ 不包含 $t$”。

单次判断复杂度 $O(nm)$，$m\le50$，$n\le10^5$，故 $O(nm\log n)$ 可接受。

C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        --a[i];  // 转为 0-based
    }

    vector<bool> deleted(n, false);

    // 检查删除前 k 次后，s 中是否仍包含 t
    auto contains_substring = [&](int k) {
        fill(deleted.begin(), deleted.end(), false);
        for (int i = 0; i < k; i++) deleted[a[i]] = true;
        // 构建前缀和，方便快速判断区间内是否有空隙
        vector<int> pre(n+1, 0);
        for (int i = 0; i < n; i++)
            pre[i+1] = pre[i] + (deleted[i] ? 1 : 0);
        for (int i = 0; i + m <= n; i++) {
            // 如果区间 [i,i+m) 中无删除
            if (pre[i+m] - pre[i] == 0) {
                bool ok = true;
                for (int j = 0; j < m; j++) {
                    if (s[i+j] != t[j]) { ok = false; break; }
                }
                if (ok) return true;
            }
        }
        return false;
    };

    int l = 0, r = n, ans = n;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (contains_substring(mid)) {
            // 仍包含，需要更多删除
            l = mid + 1;
        } else {
            ans = mid;
            r = mid - 1;
        }
    }

    cout << ans << '\n';
    return 0;
}

Python

import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    s = input().strip()
    t = input().strip()
    a = list(map(lambda x: int(x)-1, input().split()))

    deleted = [False] * n

    def contains_substring(k):
        # 标记删除前 k 次的位置
        for i in range(n): deleted[i] = False
        for i in range(k): deleted[a[i]] = True
        # 前缀和统计删除数
        pre = [0] * (n+1)
        for i in range(n): pre[i+1] = pre[i] + (1 if deleted[i] else 0)
        # 检查每个窗口
        for i in range(0, n-m+1):
            if pre[i+m] - pre[i] == 0:
                # 连续窗口中无删除
                if s[i:i+m] == t:
                    return True
        return False

    # 二分查找最小 k
    l, r, ans = 0, n, n
    while l <= r:
        mid = (l + r) // 2
        if contains_substring(mid):
            l = mid + 1
        else:
            ans = mid
            r = mid - 1
    print(ans)

if __name__ == '__main__':
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        String s = br.readLine();
        String t = br.readLine();
        int[] a = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken()) - 1;

        boolean[] deleted = new boolean[n];
        int[] pre = new int[n+1];

        // 检查删除前 k 次后是否仍包含 t
        Function<Integer, Boolean> contains_substring = (k) -> {
            Arrays.fill(deleted, false);
            for (int i = 0; i < k; i++) deleted[a[i]] = true;
            pre[0] = 0;
            for (int i = 0; i < n; i++) pre[i+1] = pre[i] + (deleted[i] ? 1 : 0);
            for (int i = 0; i + m <= n; i++) {
                if (pre[i+m] - pre[i] == 0) {
                    boolean ok = true;
                    for (int j = 0; j < m; j++) {
                        if (s.charAt(i+j) != t.charAt(j)) { ok = false; break; }
                    }
                    if (ok) return true;
                }
            }
            return false;
        };

        int l = 0, r = n, ans = n;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (contains_substring.apply(mid)) {
                l = mid + 1;
            } else {
                ans = mid;
                r = mid - 1;
            }
        }
        System.out.println(ans);
    }
}

题目内容

公司里有两个字符串，分别是 $s$ 和 $t$ 。由于数据安全的原因,字符串 $t$ 不允许作为 $s$ 的子串存在。为了满足数据规范，米小游需要按照一定的顺序删除字符串 $s$ 中的一些字符，确保 $s$ 中不再包含 $t$ 。注意删除字符 $s_i$ 后，不会自动将前后字符串合并，你可以认为使用一个空白字符代替 $s_i$ 。

米小游想知道，在保证 $s$ 不包含 $t$ 的前提下，她最少需要删除多少个字符？

删除顺序可以描述为一个排列，$a_i$ 表示删除 $s_{a_i}$ 字符。

输入描述

第一行输入两个整数 $n$ 和 $m$ ，表示字符串 $s$ 和 $t$ 的长度。

第二行输入一个长度为 $n$ 的字符串 $s$ ，仅包含小写字母。

第三行输入一个长度为 $m$ 的字符串 $t$ ，仅包含小写字母。

第四行输入一个长度为 $n$ 的排列 $a$，表示第 $i$ 次删除 $s_{a_i}$ 字符。

$1≤n≤ 10^5$

$1≤m≤50$

$1 ≤a_i ≤n$

输出描述

输出一个整数，表示最少需要删除的字符个数。

样例1

输入

5 2
ababa
ab
3 2 5 4 1

输出

2

说明

第一次删除 $S_3$ ，$s$ 变为 ab a ba。

第二次删除 $S_2$ ，$s$ 变为 a ba ba。

此时 $s$ 不包含 $t$ ，最少需要删除 $2$ 个字符。