OI-wiki 字符串专题最小表示法Minimum Representation完整解析与代码实现【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki最小表示法是 OI / ICPC 竞赛中解决「循环同构字符串最小字典序」问题的经典线性算法。本文以 OI-wiki 的官方文档为主体从循环同构的定义出发逐步推导朴素暴力做法及其退化原因再深入讲解 $O(n)$ 最小表示法的核心思想、证明过程与可运行的 C / Python 实现并补充仓库中与之关联的 Lyndon 分解求最小循环移位 等进阶视角帮助读者在赛场上熟练运用。定义最小表示法Minimum Representation是用于解决字符串最小表示问题的方法。所谓最小表示本质上是「循环同构串中的字典序最小者」它在判环、去重、字符串旋转匹配等问题中有着广泛的应用。字符串的最小表示循环同构当字符串 $S$ 中可以选定一个位置 $i$满足$$ S[i\cdots n]S[1\cdots i-1]T $$则称 $S$ 与 $T$循环同构cyclically isomorphic。直观理解把 $S$ 看作一个环从环上任意位置切开把后面的部分接到前面得到的字符串 $T$ 都与 $S$ 循环同构。例如abcd的所有循环同构串为abcd、bcda、cdab、dabc。最小表示字符串 $S$ 的最小表示定义为与 $S$ 循环同构的所有字符串中字典序最小的那个字符串。关于「字典序」的形式化定义可参考 OI-wiki 字符串基础章节 basic.md以第 $i$ 个字符作为第 $i$ 关键字进行大小比较空字符小于字符集内任何字符即 $aaa$。simple 的暴力先看一个最直观simple的做法每次比较以 $i$ 和 $j$ 开始的循环同构把当前比较到的位置记作 $k$每次遇到不一样的字符时便把字典序较大的那个起点跳过最后剩下的就是最优解。实现 Ccpp int k 0, i 0, j 1; while (k n i n j n) { if (sec[(i k) % n] sec[(j k) % n]) { k; } else { if (sec[(i k) % n] sec[(j k) % n]) i; else j; k 0; if (i j) i; } } i min(i, j); Pythonpython k, i, j 0, 0, 1 while k n and i n and j n: if sec[(i k) % n] sec[(j k) % n]: k 1 else: if sec[(i k) % n] sec[(j k) % n]: i 1 else: j 1 k 0 if i j: i 1 i min(i, j)其中sec为长度为 $n$ 的字符串下标从 0 开始% n用于模拟循环同构。循环结束后i、j中较小者即为最小表示的起始位置。解释该实现方法在随机数据下表现良好但是可以构造特殊数据卡掉。例如对于 $\texttt{aaa}\cdots\texttt{aab}$不难发现这个算法的复杂度退化为 $O(n^2)$。原因在于当两个指针的比较位置连续大量相等时k每次都要从 0 重新累积而遇到不同字符时败者指针只前进 1 位导致总比较次数逼近 $O(n^2)$。我们发现当字符串中出现多个连续重复子串时此算法效率降低。例如aaab这类「大量相同前缀 末尾不同字符」的结构会反复触发长距离的相等比较。因此我们考虑优化这个过程。最小表示法算法核心考虑对于一对字符串 $A,B$它们在原字符串 $S$ 中的起始位置分别为 $i,j$且它们的前 $k$ 个字符均相同即$$ S[i \cdots ik-1]S[j \cdots jk-1] $$不妨先考虑 $S[ik]S[jk]$ 的情况。此时我们发现起始位置下标 $l$ 满足 $i\le l\le ik$ 的字符串均不能成为答案。因为对于任意一个字符串 $S_{ip}$表示以 $ip$ 为起始位置的字符串$p \in [0, k]$一定存在字符串 $S_{jp}$ 比它更优——由于前 $k$ 位完全相等$S_{ip}$ 与 $S_{jp}$ 的前 $k-p$ 位相同而在第 $k-p$ 位处 $S_{jp}$ 的字符严格更小。所以我们比较时可以跳过下标 $l\in [i,ik]$直接比较 $S_{ik1}$。这样我们就完成了对暴力算法的核心优化败者指针不再只前进 1 位而是直接跳跃 $k1$ 位从而将大量重复子串带来的冗余比较全部跳过。时间复杂度$O(n)$。指针 $i$、$j$ 在整个过程中都单调不减每次失配至少使其中一个指针前进 $k1\ge 1$ 位因此总步数线性于 $n$。过程初始化指针 $i$ 为 $0$$j$ 为 $1$初始化匹配长度 $k$ 为 $0$。比较第 $k$ 位的大小根据比较结果跳转相应指针。若跳转后两个指针相同则随意选一个加一以保证比较的两个字符串不同。重复上述过程直到比较结束k n或某个指针越界说明已找到最小表示。答案为 $i,j$ 中较小的一个。实现 Ccpp int k 0, i 0, j 1; while (k n i n j n) { if (sec[(i k) % n] sec[(j k) % n]) { k; } else { sec[(i k) % n] sec[(j k) % n] ? i i k 1 : j j k 1; if (i j) i; k 0; } } i min(i, j); Pythonpython k, i, j 0, 0, 1 while k n and i n and j n: if sec[(i k) % n] sec[(j k) % n]: k 1 else: if sec[(i k) % n] sec[(j k) % n]: i i k 1 else: j j k 1 if i j: i 1 k 0 i min(i, j)与暴力版本相比唯一的区别在失配分支这里把i/j替换成了i i k 1/j j k 1即一次性跳过确定不可能成为最小表示的 $k1$ 个起点。返回的i即为最小表示的起始下标sec[i..n] sec[0..i]就是最小表示串。从源码看关联算法Lyndon 分解求最小循环移位最小表示问题还有另一条求解路径。在 OI-wiki 的 lyndon.md 中给出了基于Lyndon 分解的求解方法构造串 $ss$ 的 Lyndon 分解寻找一个起点小于 $n$ 且终点大于等于 $n$ 的 Lyndon 串 $t$则 $t$ 的开头即为 $s$ 的最小表示起点沿 $t$ 的开头向后取 $n$ 个字符即为最小表示。Duval 算法同样可以在 $O(n)$ 时间内完成分解其中 C 实现可见 lyndon.md 的min_cyclic_string函数。两种算法的复杂度同为 $O(n)$但适用场景略有差异本文的最小表示法双指针实现代码量更小、常数更优是竞赛中最常用的写法而 Lyndon 分解的视角则有助于在需要同时计算循环移位排名等更复杂场景下复用。典型应用场景最小表示法在实际题目中主要解决以下问题环形串最小字典序给定一个环项链、密码锁、旋转轮盘等建模求从哪个位置断开得到的线性串字典序最小循环同构去重/判定判断两个字符串是否循环同构可将两者都化为最小表示后比较字符串旋转匹配判断 $T$ 是否可由 $S$ 旋转得到等价于判断 $T$ 是否为 $SS$ 的子串且长度匹配。在实际代码中字符串读入后先求最小表示起点再输出对应子串即可。注意sec可以是任意可比较字符集上的串算法只依赖字符间的字典序比较因此对大小写字母、数字等混合串同样成立。小结最小表示法通过「失配时整体跳过确定无解的起点区间」这一关键剪枝将朴素做法的 $O(n^2)$ 最坏复杂度优化为严格的 $O(n)$是处理循环同构类问题的通用利器。建议读者将 C 与 Python 两版实现对照记忆并理解其与 Lyndon 分解 之间的内在联系做到在不同题设下都能灵活选用。更完整的字符串算法体系KMP、Manacher、后缀自动机等可继续阅读 OI-wiki 的 字符串专题索引其中每个算法均配有可运行的代码与对应样例数据位于 docs/string/code 与 docs/string/examples。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考