题目回顾

我们有两个鼓，左鼓敲击记为 L，右鼓敲击记为 R。由于奇异力量的影响，一次敲击听到的声音可能是一声，也可能是两声。也就是说，实际的敲击序列 $p$ 中的每个字符都可能“扩展”为 $1$ 个或 $2$ 个相同的字符，得到最终听到的声音序列 $s$。

给定 $p$ 和 $s$，判断 $s$ 是否可能由 $p$ 按照上述规则扩展得到。

• 敲击序列 $p$ 由 L 和 R 组成，长度 $|p| = n$。
• 听到的声音 $s$ 长度 $|s| = m$，$n \le m \le 2n$。

我们需要对每个测试用例输出 YES 或 NO。

简单情况：只有一种字符

假设 $p$ 完全由 L 组成，长度为 $x$。那么每个 L 可以变成 L 或 LL，总长度可以在 $x$（每个都选一声）到 $2x$（每个都选两声）之间任意取值。并且，因为所有字符都是 L，所以 $s$ 也只能全部是 L。因此，当 $p$ 只有 L 时，$s$ 合法的充要条件是：

1. $s$ 全部由 L 组成；
2. $x \le |s| \le 2x$。

同理，若 $p$ 只有 R，充要条件也类似。

一般化：任意 L/R 序列

实际的 $p$ 是由 L 和 R 交替组成的。我们可以将 $p$ 划分为若干个极大连续相同字符段（称为“块”或游程）。例如：

p = LLLLLRL

它的块依次为：LLLLL（5个L），R（1个R），L（1个L）。

在扩展过程中，每个块内的字符都会扩展为相同字符，且块之间保持原有的交替顺序。一个块的长度为 $a$，扩展后对应块的长度 $b$ 必须在 $[a, 2a]$ 之间。同时，$s$ 中的块数必须与 $p$ 中的块数完全相等，并且对应块的字符必须相同（这等价于首字符相同，因为块是交替的）。

这样，问题就转化为：

• 将 $p$ 和 $s$ 分别压缩成游程长度数组 $A = [a_1, a_2, \dots, a_k]$ 和 $B = [b_1, b_2, \dots, b_{k'}]$。
• 检查是否满足：
  1. $k = k'$（块数相等）；
  2. $p$ 和 $s$ 的首字符相同（这隐含了对应块的字符全部匹配，因为块是交替的）；
  3. 对于每个 $i$，有 $a_i \le b_i \le 2a_i$。

此外，由长度范围自然可推出 $n \le m \le 2n$，所以也可先做总长度剪枝。

算法步骤

1. 读入 $p$ 和 $s$，记 $n = |p|, m = |s|$。
2. 快速非法判断：
   • 若 $m < n$ 或 $m > 2n$，直接输出 NO。
   • 若 $p[0] \neq s[0]$，直接输出 NO（因为第一个块字符必须相同）。
3. 构建游程长度数组：
   • 遍历 $p$，每当字符变化时，将当前计数存入数组 $A$，并重置计数；遍历结束后将最后一个计数加入 $A$。
   • 对 $s$ 做同样操作得到 $B$。
4. 块数检查：若 $A$ 的大小与 $B$ 的大小不同，输出 NO。
5. 逐块检查：对于 $i$ 从 $0$ 到块数$-1$，检查 $A[i] \le B[i] \le 2 \cdot A[i]$。若有不满足者输出 NO。
6. 全部通过则输出 YES。

示例分析

以 $p = \text{"LR"}$ 为例：

• $n = 2$，块为：L（长度1），R（长度1）。
• 合法的 $s$ 长度必须在 $2 \sim 4$ 之间。
• 第一个块（L）可以扩展为长度 $1$ 或 $2$ 的 L；第二个块（R）可以扩展为长度 $1$ 或 $2$ 的 R。
• 组合得到：LR $(1,1)$、LRR $(1,2)$、LLR $(2,1)$、LLRR $(2,2)$。与题目描述一致。

再以 $p = \text{"LLR"}$ 为例：

• 块长度：$A = [2, 1]$。
• $s = \text{"LLLRR"}$ 的块长度为 $B = [3, 2]$。
• 检查：$2 \le 3 \le 4$？是；$1 \le 2 \le 2$？是。且块数、首字符均匹配，答案为 YES。

正确性证明

必要性：若 $s$ 由 $p$ 扩展得到，则每个敲击要么变成 $1$ 个相同字符，要么变成 $2$ 个。因此同一块内的字符必然来自同一字符的扩展，块数不会改变，且每个块的长度必然介于原长度和两倍原长度之间。首字符也必须一致。

充分性：若上述条件满足，则可按顺序对第 $i$ 个块，将多余的 $b_i - a_i$ 个字符分配到该块内的 $a_i$ 个位置中的任意几个（每个位置最多增加 $1$ 个字符），即总能构造出合法的扩展方式。因此条件充要。

复杂度分析

• 时间复杂度：对于每个测试用例，我们只需分别扫描 $p$ 和 $s$ 一次，提取游程长度，再做一次遍历检查。总复杂度为 $O(|p| + |s|)$。题目保证所有测试用例的 $|s|$ 之和不超过 $2\times 10^5$，所以可以在时限内轻松完成。
• 空间复杂度：存储游程长度数组需要 $O(|p| + |s|)$ 的额外空间，但也可以压缩后即时比较，空间可优化到 $O(1)$。考虑到实现简单，通常直接使用 vector。

标准程序

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

void solve() {
    string a, b; cin >> a >> b;
    int n = a.size();
    int m = b.size();
    if (m < n || m > 2 * n || a[0] != b[0]) {
        cout << "NO\n";
        return;
    }
    vector<int> aa, bb;
    int cnt = 1;
    for (int i = 1; i < n; i++) {
        if (a[i] != a[i-1]) {
            aa.push_back(cnt);
            cnt = 1;
        }
        else cnt++;
    }
    aa.push_back(cnt);
    cnt = 1;
    for (int i = 1; i < m; i++) {
        if (b[i] != b[i-1]) {
            bb.push_back(cnt);
            cnt = 1;
        }
        else cnt++;
    }
    bb.push_back(cnt);
    if (aa.size() != bb.size()) {
        cout << "NO\n";
        return;
    }
    n = aa.size();
    for (int i = 0; i < n; i++) {
        if (aa[i] > bb[i] || aa[i] * 2 < bb[i]) {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}