AI042. BPE 子词合并训练

import sys


def solve() -> None:
    lines = sys.stdin.read().split("\n")
    if not lines or not lines[0].strip():
        return
    w, r_rounds = map(int, lines[0].split())
    words = []
    for i in range(1, w + 1):
        parts = lines[i].split()
        words.append((int(parts[0]), list(parts[1])))
    out = []
    for _ in range(r_rounds):
        cnt = {}
        for freq, syms in words:
            for i in range(len(syms) - 1):
                key = (syms[i], syms[i + 1])
                cnt[key] = cnt.get(key, 0) + freq
        if not cnt:
            break
        # 次数最高;并列取 (A,B) 字典序小
        best = min(cnt.items(), key=lambda kv: (-kv[1], kv[0]))
        (a, b), c = best
        out.append(f"{a}+{b} {c}")
        for idx in range(len(words)):
            freq, syms = words[idx]
            ns = []
            i = 0
            while i < len(syms):
                if i + 1 < len(syms) and syms[i] == a and syms[i + 1] == b:
                    ns.append(a + b)
                    i += 2
                else:
                    ns.append(syms[i])
                    i += 1
            words[idx] = (freq, ns)
    for _, syms in words:
        out.append(" ".join(syms))
    sys.stdout.write("\n".join(out) + "\n")


solve()