From S To T 题解

xvl- / 2023-08-05 / 原文

题目传送门

一道模拟题。

首先判断 \(s\) 是否是 \(t\) 的子序列，如果不是就直接输出 NO。证明一下，\(s\) 一定是 \(s\) 插入 \(p\) 后得到的字符串的子序列，但如果 \(s\) 不是 \(t\) 的子序列，则插入后的字符串一定不等于 \(t\)。

如果 \(s\) 是 \(t\) 的子序列，我们统计一下 \(t\) 中的其他字符共有多少个，如果 \(p\) 中的数量足够就输出 YES，否则输出 NO。

Code

#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
int q, numt[30], nump[30];
signed main() {
    ios :: sync_with_stdio(0);
    cin >> q;
    while (q--) {
        memset(numt, 0, sizeof(numt));
        memset(nump, 0, sizeof(nump));
        int cnt = 0;
        string s, t, p;
        cin >> s >> t >> p;
        for (int i = 0; i < t.size(); i++) {
            if (t[i] == s[cnt]) cnt++;
        }
        if (cnt != s.size()) cout << "NO\n";
        else {
            bool flag = 1;
            cnt = 0;
            for (int i = 0; i < t.size(); i++) {
                if (t[i] == s[cnt]) {
                    cnt++;
                    continue;
                }
                numt[t[i] - 'a' + 1]++;
            }
            for (int i = 0; i < p.size(); i++) nump[p[i] - 'a' + 1]++;
            for (int i = 1; i <= 26; i++) {
                if (nump[i] < numt[i]) flag = 0;
            }
            if (flag) cout << "YES\n";
            else cout << "NO\n";
        }
    }
    return 0;
}