文本规则模拟与 BPE 子词合并

def bpe_train(words, rounds):
    # words: [(词, 词频)]；每轮：加权统计相邻符号对 → 取最高（并列取字典序小）→ 每词从左到右不重叠合并；统计不到相邻对就提前结束
    seqs = [(list(w), f) for w, f in words]          # 每个词拆成单字符符号序列
    merges = []
    for _ in range(rounds):
        count = {}
        for syms, f in seqs:
            for i in range(len(syms) - 1):           # 重叠也计：aaa 的 (a,a) 计 2 次
                pair = (syms[i], syms[i + 1])
                count[pair] = count.get(pair, 0) + f
        if not count:
            break                                    # 没有任何相邻对：提前结束
        best = min(count, key=lambda p: (-count[p], p[0], p[1]))   # 次数最高；并列先比 A 再比 B（字符串字典序）
        merges.append(f"{best[0]}+{best[1]} {count[best]}")
        new_seqs = []
        for syms, f in seqs:                         # 从左到右不重叠合并
            out, i = [], 0
            while i < len(syms):
                if i + 1 < len(syms) and (syms[i], syms[i + 1]) == best:
                    out.append(syms[i] + syms[i + 1])
                    i += 2
                else:
                    out.append(syms[i])
                    i += 1
            new_seqs.append((out, f))
        seqs = new_seqs
    return merges, [" ".join(syms) for syms, _ in seqs]

m, s = bpe_train([("abab", 3), ("abc", 2)], 2)
assert m == ["a+b 8", "ab+ab 3"] and s == ["abab", "ab c"]        # 样例 1（第 05 节两轮表）
m, s = bpe_train([("ab", 2), ("cd", 2)], 1)
assert m == ["a+b 2"] and s == ["ab", "c d"]                       # 样例 2：并列取字典序小
m, s = bpe_train([("aaa", 1)], 1)
assert m == ["a+a 2"] and s == ["aa a"]                            # 重叠计 2 次；合并从左不重叠
m, s = bpe_train([("a", 5), ("b", 1)], 3)
assert m == [] and s == ["a", "b"]                                 # 统计不到相邻对：提前结束，不补空轮
m, s = bpe_train([("abab", 3), ("abc", 2)], 5)
assert m == ["a+b 8", "ab+ab 3", "ab+c 2"] and s == ["abab", "abc"]  # 第 3 轮后再无相邻对，第 4 轮提前结束

五条断言覆盖两组样例、重叠计数、提前结束与「R 大于实际轮数」。完整程序（含读入与输出）在下一个展开区。

import sys

data = sys.stdin.read().split("\n")
w, R = map(int, data[0].split())
words = []                                        # 每个词：(词频, 符号列表)，初始每个字符一个符号
for line in data[1:1 + w]:
    freq, word = line.split()
    words.append((int(freq), list(word)))
merges = []                                       # 每轮实际执行的合并：「A+B 次数」
for _ in range(R):
    count = {}                                    # 规则 ①：加权统计相邻符号对（重叠位置各计一次，权重是词频）
    for freq, syms in words:
        for i in range(len(syms) - 1):
            pair = (syms[i], syms[i + 1])
            count[pair] = count.get(pair, 0) + freq
    if not count:                                 # 规则 ④：统计不到任何相邻对，提前结束
        break
    best = min(count, key=lambda p: (-count[p], p[0], p[1]))   # 规则 ②：次数最高；并列先比 A 再比 B（字符串字典序）
    merges.append(f"{best[0]}+{best[1]} {count[best]}")
    for idx in range(w):                          # 规则 ③：每个词从左到右不重叠合并
        freq, syms = words[idx]
        out, i = [], 0
        while i < len(syms):
            if i + 1 < len(syms) and (syms[i], syms[i + 1]) == best:
                out.append(syms[i] + syms[i + 1])
                i += 2
            else:
                out.append(syms[i])
                i += 1
        words[idx] = (freq, out)
for line in merges:                               # 先输出每轮一行，再按输入顺序输出各词最终切分
    print(line)
for _, syms in words:
    print(" ".join(syms))

四条规则各对应一段带编号注释的代码。用两组样例、1 1 / 5 aaa → a+a 10 / aa a（重叠计 2 次、合并不重叠）、1 3 / 4 ab → a+b 4 / ab（第 2 轮提前结束）核对。

import sys

lines = sys.stdin.read().split("\n")
text = lines[0].strip()
words = set(lines[1].strip().split(","))          # 词库：集合查询
max_len = max((len(w) for w in words), default=1)
out = []
for seg in text.replace(",", " ").replace(".", " ").replace(";", " ").split():   # 标点只断句，不成词
    n = len(seg)
    i = 0
    while i < n:                                  # 顺序优先：从当前位置往后
        j = min(n, i + max_len)
        while j > i and seg[i:j] not in words:    # 最长匹配：长度从大到小试
            j -= 1
        if j > i:
            out.append(seg[i:j])
            i = j
        else:                                     # 一个都不命中：单个字母成词
            out.append(seg[i])
            i += 1
print(",".join(out))

用三组题面示例核对；思路与题目页参考题解相同（标点替换成空格再切分）。

import sys

cells = sys.stdin.readline().rstrip("\n").split(",")
n = len(cells)
names = [chr(ord("A") + i) for i in range(n)]
parsed = {}                                       # 单元格 → (引用前, 引用的单元格或 "", 引用后)


def parse(s):                                     # 至多一对 <X>，X 必须是存在的单元格；否则返回 None
    if s.count("<") == 0 and s.count(">") == 0:
        return (s, "", "")
    if s.count("<") != 1 or s.count(">") != 1:
        return None
    l, r = s.index("<"), s.index(">")
    if l > r:
        return None
    ref = s[l + 1:r]
    if ref not in names:
        return None
    return (s[:l], ref, s[r + 1:])


ok = True
for name, s in zip(names, cells):
    p = parse(s)
    if p is None:
        ok = False
        break
    parsed[name] = p

value = {}                                        # 已展开的单元格
state = {}                                        # 1 = 展开中（再遇到就是环），2 = 完成


def expand(name):                                 # 记忆化展开；自引用 / 循环引用返回 None
    if state.get(name) == 2:
        return value[name]
    if state.get(name) == 1:
        return None
    state[name] = 1
    before, ref, after = parsed[name]
    if ref == "":
        value[name] = before
    else:
        inner = expand(ref)
        if inner is None:
            return None
        value[name] = before + inner + after
    state[name] = 2
    return value[name]


if ok:
    for name in names:
        if expand(name) is None:
            ok = False
            break
print(",".join(value[name] for name in names) if ok else -1)

用第 07 节的 1,2<A>00,3<B>4 → 1,2100,321004 和五类异常各一组核对；题目页参考题解用拓扑排序判环，结果相同。

def segment(text, words):
    # text 只含小写字母与 , . ; 三种标点；words 是词库集合；顺序优先 + 最长匹配，未命中按单个字母
    max_len = max((len(w) for w in words), default=1)
    out = []
    for seg in text.replace(",", " ").replace(".", " ").replace(";", " ").split():
        n, i = len(seg), 0
        while i < n:
            j = min(n, i + max_len)
            while j > i and seg[i:j] not in words:
                j -= 1
            if j > i:
                out.append(seg[i:j]); i = j
            else:
                out.append(seg[i]); i += 1
    return out

D = {"i", "love", "china", "ch", "na", "ve", "lo", "this", "is", "the", "word", "beauti", "tiful", "ful"}
assert segment("ilovechina", D) == ["i", "love", "china"]                      # 题面示例 1：词库里没有 ilove
assert segment("iat", D) == ["i", "a", "t"]                                     # 示例 2：未命中按单个字母
assert segment("ilovechina,thewordisbeautiful", D) == ["i", "love", "china", "the", "word", "is", "beauti", "ful"]   # 示例 3：标点只断句
assert segment("ilovechina", {"i", "ilove", "lo", "love", "ch", "china", "lovechina"}) == ["ilove", "china"]   # 题面说明的例子：最长匹配

长度上限用词库最长词长，避免每次都从整段长度试起。