Hướng dẫn giải

Mỗi cặp $(s, t)$: $s$ là từ thầy đoán, $t$ là từ Bình gõ. Khi gõ một phím hỏng, ký tự tương ứng có thể xuất hiện nhiều lần liên tiếp, nhưng vẫn phải xuất hiện ít nhất một lần. Cần kiểm tra $t$ có thể là kết quả gõ từ $s$ hay không.

Nói cách khác, $t$ phải được tạo ra bằng cách thay mỗi ký tự của $s$ bằng một dãy liên tiếp gồm một hoặc nhiều ký tự giống nó.

Ví dụ: hello khớp với helloo (ký tự o cuối lặp lại), nhưng không khớp với helo (thiếu một chữ l) hay hlllloo (thiếu chữ e).

Sub 1: Quy hoạch động — ~O(|s| \cdot |t|)~, dùng khi ~|s|, |t| \le 300~

Gọi $dp[i][j]$ là đúng nếu $t[0..j)$ tạo được từ $s[0..i)$. Có hai cách chuyển:

• Ký tự $t[j]$ là lần gõ đầu tiên của $s[i]$: nếu $t[j] = s[i]$ thì $dp[i+1][j+1]$ đúng.
• Ký tự $t[j]$ kéo dài lần gõ của $s[i-1]$: nếu $t[j] = s[i-1]$ thì $dp[i][j+1]$ đúng.

Đáp án là $dp[|s|][|t|]$.

Kết quả chấm riêng sub này: đúng 17/21 test (4 test quá giờ vì độ dài vượt miền của sub).

Sub 2: Hai con trỏ — ~O(|s| + |t|)~

Duyệt $t$ bằng chỉ số $j$, và giữ chỉ số $i$ trong $s$. Ở mỗi bước:

• Nếu $s[i] = t[j]$ thì cả hai cùng tiến một bước.
• Nếu không, nhưng $t[j]$ giống $t[j-1]$ thì đây là gõ kéo dài, chỉ tiến $j$.
• Ngược lại, không khớp.

Khi duyệt xong $t$, $t$ khớp nếu đã dùng hết $s$.

Bẫy cần chú ý: phải kiểm tra $i = |s|$ ở cuối, vì có thể $t$ đã hết nhưng $s$ còn ký tự chưa được gõ. Cũng cần chú ý lặp lại ký tự trong $s$ (như ll trong hello) có thể được gõ thành một dãy dài hơn.

Kết quả chấm riêng sub này: đúng 21/21 test.

Chương trình hoàn chỉnh

Chương trình đọc $n$, rồi với mỗi cặp $(s, t)$ gọi sub1 nếu cả hai độ dài không quá $300$, ngược lại gọi sub2, và in YES hoặc NO. Khi đi thi nên viết như vậy: sub1 vẫn ăn điểm các test nhỏ nếu sub2 chưa làm kịp.

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

string s, t;   // s: từ thầy đoán, t: từ Bình gõ

// Sub 1: quy hoạch động — dp[i][j] = đúng nếu t[0..j) có thể tạo ra từ s[0..i)
// Mỗi ký tự s[i] tạo ra ít nhất một ký tự liên tiếp giống nhau trong t.
// Độ phức tạp O(|s| * |t|). Dùng khi |s|, |t| <= 300
void sub1() {
    int m = s.size(), k = t.size();
    vector<vector<char>> dp(m + 1, vector<char>(k + 1, 0));
    dp[0][0] = 1;
    for (int i = 0; i <= m; i++)
        for (int j = 0; j <= k; j++) {
            if (!dp[i][j]) continue;
            // Ký tự t[j] là lần gõ đầu tiên của s[i]
            if (i < m && j < k && t[j] == s[i]) dp[i + 1][j + 1] = 1;
            // Ký tự t[j] kéo dài lần gõ của s[i-1] (cùng ký tự với nó)
            if (i > 0 && j > 0 && j < k && t[j] == s[i - 1]) dp[i][j + 1] = 1;
        }
    cout << (dp[m][k] ? "YES" : "NO") << "\n";
}

// Sub 2: hai con trỏ — đi qua t, khớp với s, và ký tự nào lặp lại ký tự ngay trước nó thì coi là gõ kéo dài.
// Độ phức tạp O(|s| + |t|). Dùng cho mọi độ dài
void sub2() {
    int m = s.size(), k = t.size();
    int i = 0, j = 0;
    while (j < k) {
        if (i < m && s[i] == t[j]) { i++; j++; }                    // khớp ký tự tiếp theo của s
        else if (j > 0 && t[j] == t[j - 1]) j++;                     // kéo dài ký tự vừa gõ
        else { cout << "NO\n"; return; }
    }
    cout << (i == m ? "YES" : "NO") << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    while (n--) {
        cin >> s >> t;
        if (s.size() <= 300 && t.size() <= 300) sub1();   // độ dài nhỏ: DP cho chắc
        else sub2();
    }
    return 0;
}