Codeforces round 1017 (Div.4)

D

题目描述

点击跳转

回顾反思 & 代码思路

暴力就要必须要考虑到所有情况。赛时忽略了p串可能会比s串多出一截———当p串处理完后，s串可能还会有一段，这种情况下结果应是NO,但是如果只是遍历一遍p串，可能会因为缺少判断s.szie()而输出错误答案。

判别条件也很简单，按照题意，设ip是读p串当前字母的个数，is是读s串当前字母的个数，那么应该符合公式：
is \leqslant ip \leqslant 2 \times is

代码

#include <iostream>
#include <string>
using namespace std;

#define akitama return 0
#define ll long long int

void solve() {
    string p, s;
    cin >> p >> s;
    int ip = 0, is = 0;
    int j = 0;
    for (int i = 0; i < p.size();) {
        ip = i + 1;
        while (ip < p.size() && p[i] == p[ip]) ip++;
        is = j + 1;
        while (is < s.size() && s[j] == s[is]) is++;
        if (j >= s.size() || p[i] != s[j] || is - j > (ip - i) * 2 || is - j < ip - i) {
            cout << "NO\n";
            return;
        }
        i = ip;
        j = is;
    }
    if (j != s.size()) {
        cout << "NO\n";
        return;
    }
    cout << "YES\n";
}

signed main() {
    cin.tie(nullptr)->ios::sync_with_stdio(false);
    int _; cin >> _;
    while (_) { solve(); _--; }
    akitama;
}