解题思路

本题要求模拟 $BPE$ 的迭代合并过程。

初始时，字符串 $S$ 中的每个字符都是一个独立的 $Token$。每一轮操作分为三步：

1. 统计当前序列中所有相邻 $Token$ 对的出现次数。
2. 找到出现频率最高的相邻对。

题目内容

某大型语言模型（$LLM$）无法直接理解文本，它需要将文本切分成一个个“$Token$”，最常用的分词算法是 $BPE（Byte$ $Pair$ $Encoding$）。

$BPE$ 的核心思想是：迭代合并最高频的相邻字符对。

例如，给定初始字符串 “$h$ $u$ $g$ $h$ $u$ $g$” 中，“$u$” 和 “$g$” 相邻出现了两次，频率最高，合并后为 “$h$ $ug$ $h$ $ug$”。

给定一个初始的字符串 $S$（由小写英文字母组成）和一个整数 $K$（最大合并次数），请模拟 $BPE$ 算法的 $K$ 次迭代过程，输出最终的 $Token$ 序列。

迭代规则

在每一轮迭代中：

1. 统计频率：统计当前序列中所有相邻 Token 对的出现频率。

2. 选择最优对：找出频率最高的相邻对。

• $Tie-breaking$ (平局处理) ：如果存在多个频率相同的最高频对，选择字典序最小的那一对（例如：$(a,b)$ 比 $(c,d)$ 小；$(a,b)$ 比 $(a,c)$ 小）。
• 终止条件：如果最高频率为 $1$（即所有相邻对都只出现一次），或者没有相邻对，则提前终止迭代。

3. 合并：将序列中所有出现的“最佳对”合并为一个新的 $Token$。合并时采用从左到右贪心原则（即遇到匹配就合并，跳过下一个，继续扫描）。

输入描述

• 第一行：包含一个整数 $K（0 ≤ K ≤ 100）$，表示最大合并次数。

• 第二行：包含一个字符串 $S$，由小写英文字母组成。

  • 注意：初始状态下，我们将字符串 $S$ 中的每个字符视为一个独立的 $Token$。
  • $S$ 的长度范围：$1 ≤ |S| ≤ 1000$

输出描述

输出一行，表示经过最多 $K$ 次合并后的 $Token$ 序列，$Token$ 之间用空格分隔。

样例1

输入

5
aaabdaaabac

输出

aaab d aaab a c

说明

1. 初始：$a$ $a$ $a$ $b$ $d$ $a$ $a$ $a$ $b$ $a$ $c$

2. $Merge$ $1$: $('a','a')$ 最多，序列变为 $aa$ $a$ $b$ $d$ $aa$ $b$ $a$ $c$（注意贪心合并，前两个 $a$ 合并，第三个落单）。

3. $Merge$ $2$: $('aa', 'a')$ 最多，序列变为 $aab$ $b$ $d$ $aaa$ $b$ $a$ $c$。

4. $Merge$ $3$: $('aaa','b')$ 最多，序列变为 $aaab$ $d$ $aaab$ $a$ $c$。

5. 后续频率均为 $1$，停止。

样例2

输入

2
ababac

输出

ab ab a c

说明

1. 初始序列：$['a', 'b', 'a', 'b', 'a', 'c']$
2. 第1轮：
   • 相邻对： $('a','b')=2$ 次，$('b','a')=2$ 次，$('a','c')=1$ 次。
   • 最高频是 $2$。$('a','b')$ 和 $('b','a')$ 频率相同。
   • 字典序比较：$'a'＜'b'$，所以选择 $('a','b')$。
   • 合并后序列：$['ab', 'ab', 'a', 'c']$
3. 第2轮：

• 相邻对 $('ab','ab')=1$ 次，$('ab','a')=1$ 次...
  • 最高频均 $1$，触发终止条件。

4. 最终输出：$ab$ $ab$ $a$ $c$