Editorial for Máy In Kẹt Phím


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Nghaiz

Lời giải: Máy In Nhãn Kẹt Phím

Chủ đề: xử lý chuỗi (string), duyệt bằng for

Tóm tắt đề

Cho tên \(s\) và nhãn \(t\). Mỗi ký tự của \(s\) khi gõ sẽ được in ra \(1\) hoặc nhiều lần liên tiếp. Hỏi \(t\) có thể là kết quả in của \(s\) hay không.

Nhận xét then chốt: chia chuỗi thành các "nhóm"

Gom các ký tự giống nhau đứng liền nhau thành nhóm, mỗi nhóm ghi lại (ký tự, số lần lặp):

  • anna → (a,1) (n,2) (a,1)
  • aanaa → (a,2) (n,1) (a,2)

Khi gõ một nhóm \((c, k)\) trong tên, nhân viên nhấn phím \(c\) đúng \(k\) lần, mỗi lần in ra ít nhất một chữ \(c\). Kết quả là một nhóm \((c, k')\) trong nhãn với \(k' \geq k\). Hai nhóm liền nhau trong tên có ký tự khác nhau, nên khi in ra chúng không bao giờ dính vào nhau.

Vậy \(t\) là nhãn hợp lệ của \(s\) khi và chỉ khi:

  1. \(s\) và \(t\) có cùng số nhóm;
  2. nhóm thứ \(i\) của hai chuỗi có cùng ký tự;
  3. số lần lặp trong nhóm thứ \(i\) của \(t\) không nhỏ hơn của \(s\).

Cài đặt

def nen(s):
    nhom = []
    for ch in s:
        if nhom and nhom[-1][0] == ch:
            nhom[-1][1] += 1
        else:
            nhom.append([ch, 1])
    return nhom

Sau đó so sánh từng cặp nhóm bằng zip. Có thể dùng itertools.groupby cho gọn:

from itertools import groupby
nhom = [(c, len(list(g))) for c, g in groupby(s)]

Độ phức tạp

\(O(|s| + |t|)\) cho mỗi câu hỏi, tổng cộng tuyến tính theo kích thước input.

Code mẫu

import sys


def nen(s):
    nhom = []
    for ch in s:
        if nhom and nhom[-1][0] == ch:
            nhom[-1][1] += 1
        else:
            nhom.append([ch, 1])
    return nhom


def co_the_in(ten, nhan):
    a, b = nen(ten), nen(nhan)
    if len(a) != len(b):
        return False
    for (c1, k1), (c2, k2) in zip(a, b):
        if c1 != c2 or k2 < k1:
            return False
    return True


def main():
    data = sys.stdin.read().split()
    t = int(data[0])
    kq = []
    for i in range(t):
        ten, nhan = data[1 + 2 * i], data[2 + 2 * i]
        kq.append("YES" if co_the_in(ten, nhan) else "NO")
    print("\n".join(kq))


main()

Comments

There are no comments at the moment.