🐨 | CF1898E

Pawbert · 2023-11-25 15:10:07 · 题解

考虑没有排序操作的情况：枚举 t 的每一个字符 t_i，匹配第一个 s_j=t_i，并删去 s[1..j]，若中途无法匹配则无解。这个贪心的正确性在于每次选第一个使得后面选的机会最大化。

现在加入了排序，发现一段字符排序之后是不可逆的，所以我们尽量保证每次匹配操作后 s 保持原来的顺序。同样的，我们每次找到第一个 s_j=t_i，对于 s_k<s_j(k<j)，这些字符以后肯定是无法匹配的，因为如何排序 s_k 必然在 s_j 前面。于是我们删除这些 s_k，为了保持原来顺序，每次把 s_j 与前一个字符交换（排序），一直交换到开头，这里保证了后面机会选择的最大化。

每个字符的出现位置用队列维护，时间复杂度 \mathcal O(|\Sigma|m)。

const int maxn = 2e5 + 10;
int n, m; char s[maxn], t[maxn]; queue<int> q[26];

void work() {
    n = read(), m = read();
    scanf("%s %s", s + 1, t + 1);

    for (int i = 0; i < 26; i ++) while (!q[i].empty()) q[i].pop();
    for (int i = 1; i <= n; i ++) q[s[i] - 'a'].push(i);
    for (int i = 1; i <= m; i ++) {
        int c = t[i] - 'a', id;
        if (q[c].empty()) return printf("NO\n"), void();

        id = q[c].front(), q[c].pop();
        for (int j = 0; j < c; j ++)
            while (!q[j].empty() && q[j].front() < id) q[j].pop();
    }

    printf("YES\n");
}