1. 问题转化

我们可以把问题看作在一个状态图上做 BFS 找最短路径。

状态定义： 状态可以用当前剩余的二进制串来表示，但这样状态太多。 更好的方法：

状态 $(x, y)$ 表示：我们已经匹配了某个二进制串的前面部分，现在有两个并行的解码路径，一个路径剩余未匹配的二进制串是 $x$，另一个路径剩余未匹配的二进制串是 $y$。

初始状态：$( \text{空串}, \text{空串} )$，表示两个路径都完全匹配，还没有开始分歧。

目标状态：存在某个状态 $(x, y)$ 其中 $x$ 和 $y$ 都是空串，且到达该状态的过程中两个路径选择的符号序列不同（即不是一直同步解码同一个符号）。

但是这样直接做状态空间还是很大。

2. 更高效的状态表示

实际上，我们可以把状态定义为 $(a, b)$，其中 $a$ 和 $b$ 是某个编码的后缀。 含义：

我们有两个解码路径，一个路径比另一个路径多解码了一些内容，导致一个路径的剩余待匹配串是 $a$，另一个是 $b$。

特别地，如果 $a$ 是 $b$ 的前缀，说明第一个路径比第二个路径领先一些；反之亦然。

我们关心的是两个路径的剩余待匹配串，因为我们要让它们最终同时结束（即两个剩余串都为空），并且中间选择的符号序列不同。

BFS 状态：

状态 $(u, v)$ 表示两个解码路径的“剩余二进制串”。

初始状态：$(\varepsilon, \varepsilon)$（两个空串）。

转移：从 $(u, v)$ 出发，我们尝试在 $u$ 后面添加一个完整的编码 $c$，或者在 $v$ 后面添加一个完整的编码 $c$，然后看新的剩余串是什么。

目标：到达 $(\varepsilon, \varepsilon)$ 且步数（已解码的二进制长度）> 0，并且两个路径的符号序列不同。

3. 具体 BFS 过程

我们维护一个队列，初始状态 $("", "")$，距离 0。

对于每个状态 $(u, v)$：

如果 $u$ 和 $v$ 都是空，且从初始状态到这里的路径长度 > 0，并且两个路径的符号序列不同，则找到答案。

否则，尝试扩展：

如果 $u$ 是 $v$ 的前缀（且 $u \neq v$），则我们可以给第二个路径添加一个编码 $c$，使得 $c$ 的前缀是 $v$ 去掉 $u$ 的部分，这样两个路径的剩余串会更新。

如果 $v$ 是 $u$ 的前缀（且 $u \neq v$），对称处理。

如果 $u$ 和 $v$ 没有前缀关系，则这个状态无法继续（因为二进制序列必须一致）。

如果 $u == v$ 且非空，则两个路径剩余相同，可以同时添加同一个编码（但这样不会产生不同序列，除非后面分开）。

更简单的方法： 我们直接模拟同时扩展两个路径，每次给某个路径添加一个编码，然后看两个剩余串的关系。

4. 最终采用的算法

我们 BFS 的状态是 $(s, t)$，表示两个路径的剩余二进制串。 初始：$("", "")$。 每次从队列取出 $(s, t)$：

如果 $s == ""$ 且 $t == ""$ 且 从开始到这里的步数 > 0，则检查两个路径的符号序列是否不同，如果是，则返回当前步数。

否则，如果 $s$ 是 $t$ 的前缀（包括 $s == t$）：

我们可以给第二个路径添加一个编码 $code$，要求 $code$ 的前缀等于 $t$ 去掉 $s$ 的部分（即 $t[len(s):]$），这样新的剩余串是 $( "", code[len(t)-len(s):] )$。

如果 $t$ 是 $s$ 的前缀（包括 $t == s$）：

对称处理。

如果 $s$ 和 $t$ 没有前缀关系，则无法继续。

但这样实现较复杂，更简单的方法是直接枚举给哪个路径加编码，然后看新的剩余串。

5. 简化版 BFS

我们维护队列中的状态 $(x, y)$ 表示两个路径的已解码二进制长度差的剩余部分。 实际上，我们可以把状态定义为两个当前累积的二进制串，但长度可能很大。 更好的办法：状态 $(diff, len)$ 不太可行，因为 diff 是二进制串。

最终标准解法： 状态为 $(pref, i, j)$ 不太现实。 实际上标准解法是：

用 BFS，状态为 $(a, b)$ 其中 $a$ 和 $b$ 是某个编码的前缀。

初始 $("", "")$。

转移：选一个路径，给它加上一个编码 $p$，看新的前缀关系。

用 vis[a][b] 记录访问过，避免重复。

当 $a == ""$ 且 $b == ""$ 且 步数 > 0 时，检查是否来自不同符号序列。

复杂度

状态数：$O((NM)^2)$ 因为 $a$ 和 $b$ 都是某个编码的前缀，长度 ≤ M，最多 N*M 种。

BFS 每次转移尝试 N 个编码。

总复杂度 $O(N^3 M^2)$ 在 N,M ≤ 50 时可接受。