OI-wiki 字符串专题Main–Lorentz 算法——用分治与 Z 函数在 O(n log n) 时间内找出字符串全部重串【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读给定一个长度为 $n$ 的字符串 $s$如何找出其中所有由两个相同子串拼接而成的重串tandem repetition本文以 OI-wiki 仓库中 docs/string/main-lorentz.md 为主体系统讲解 Michael Main 与 Richard J. Lorentz 于 1982 年提出的 Main–Lorentz 算法它以分治为骨架、以Z 函数为加速工具将原本可能多达 $O(n^2)$ 个的重串压缩进 $O(n \log n)$ 个四元组中。读完本文你将掌握重串的精确定义与计数结论、左偏/右偏交叉重串的判定充要条件以及一份可复制的完整 C 实现并能够根据四元组输出所有重串的起止位置或只求其数量与最长者。什么是重串Tandem Repetition定义与记号给定一个长度为 $n$ 的字符串 $s$。我们将一个字符串连续写两遍所产生的新字符串称为重串tandem repetition。为表述精准被重复的那个字符串称为原串。换言之一个重串等价于一对下标 $(i, j)$它使得 $s[i \dots j]$ 是两个相同字符串拼接而成。例如字符串 $\tt acababaee$ 包含三个重串$s[2 \dots 5]\tt abab$、$s[3 \dots 6]\tt baba$、$s[7 \dots 8]\tt ee$字符串 $\tt abaaba$ 只有两个重串$s[0 \dots 5]\tt abaaba$、$s[2 \dots 3]\tt aa$。你的目标通常是两类问题找出字符串 $s$ 中所有的重串较简单的问题找到 $s$ 中任意一个重串或者最长的一个重串。本文讨论的算法由 Michael Main 和 Richard J. Lorentz 在 1982 年提出能够以前者全部重串为目标同时覆盖后者。约定下文所有字符串下标从 $0$ 开始记 $\overline{s}$ 为 $s$ 的反串如 $\overline{\tt abc} \tt cba$。重串的个数为什么需要压缩表示一个长度为 $n$ 的字符串可能有多达 $O(n^2)$ 个重串。一个显然的例子是 $n$ 个字符全部相同的字符串——此时只要子串长度为偶数该子串就是重串。多数情况下周期较小的周期字符串都会包含大量重串。但这并不妨碍我们在 $O(n \log n)$ 时间内计算出重串数量关键在于算法通过某种压缩形式来表达重串使得多个重串可以被合并为一个。关于重串数量有以下三个有趣结论如果某个重串的原串本身不是重串则称它为本原重串primitive repetition。可以证明本原重串最多有 $O(n \log n)$ 个。若将重串用Crochemore 三元组$(i, p, r)$ 压缩——其中 $i$ 是重串的起始位置$p$ 是某个循环节的长度注意不是原串长度$r$ 为该循环节重复的次数——则一个字符串的所有重串可以被 $O(n \log n)$ 个 Crochemore 三元组表示。Fibonacci 字符串定义如下 $$ \begin{align} t_0 a, \ t_1 b, \ t_i t_{i-1} t_{i-2}, \end{align} $$ Fibonacci 字符串具有高度周期性。对于长度为 $f_i$ 的 Fibonacci 字符串 $t_i$即使使用 Crochemore 三元组压缩也需要 $O(f_i \log f_i)$ 个三元组其本原重串的数量同样为 $O(f_i \log f_i)$ 个——这说明 $O(n \log n)$ 这个界是紧的。Main–Lorentz 算法总览核心思想分治Main–Lorentz 算法的核心思想是分治与归并排序有着相似的递归骨架将字符串划分为左部与右部递归计算完全处于左部或右部的重串数量计算起始位置在左部、终止位置在右部的重串数量——这类重串在下文中称为交叉重串crossing repetitions。其中计算交叉重串的数量是 Main–Lorentz 算法的关键点下文将详细展开。递归边界是长度为 $1$ 的字符串单个字符不可能构成重串直接返回。交叉重串的左右偏移记某字符串的左部为 $u$右部为 $v$则 $s u v$且 $u, v$ 的长度大约等于 $s$ 长度的一半通常取 $|u| \lfloor n/2 \rfloor$$|v| n - |u|$。对于任意一个重串考虑它的中间字符——定义为一个重串右半边的第一个字符即若 $s[i \dots j]$ 是重串则其中间字符为 $s[(ij1)/2]$若中间字符落在 $u$ 中则称该重串左偏left若中间字符落在 $v$ 中则称该重串右偏right。下面先详细推导如何找出所有左偏重串右偏重串的处理与之几乎完全对称。左偏重串固定 cntr 的判定方法观察中间字符固定了长度考虑一个左偏重串。令其长度为 $2l$并考察该重串第一个落入 $v$ 的字符即 $s[|u|]$。由于重串的两个半段完全相同这个字符一定与 $u$ 中的某个字符 $u[\textit{cntr}]$ 一致。于是我们固定这个位置 $\textit{cntr}$尝试找出所有符合条件的重串。例如对字符串 $\tt c ; \underset{\textit{cntr}}{a} ; c ; | ; a ; d ; a$|用于分隔左右两半 $u$ 与 $v$固定 $\textit{cntr}1$可以发现重串 $\tt caca$ 符合要求。关键观察是一旦固定了 $\textit{cntr}$重串的长度 $2l$ 也随之固定因为重串必须恰好跨越分界点 $|u|$故 $l |u| - \textit{cntr}$。因此只要我们知道如何对单个 $\textit{cntr}$ 找出全部重串就能从 $0$ 到 $|u|-1$ 枚举 $\textit{cntr}$从而覆盖所有左偏重串。判定充要条件即使固定了 $\textit{cntr}$仍然可能有多个符合条件的重串——它们的差别在于左右两段如何分配。再看一个例子字符串 $\tt abcabcac$ 中的重串 $$ \overbrace{\tt a}^{l_1}; \overbrace{\underset{\textit{cntr}}{\tt b} \tt c}^{l_2}; \overbrace{\tt a}^{l_1} ; | ; \overbrace{\tt b ; \tt c}^{l_2} $$ 记 $l_1$ 为该重串首字符到 $s[\textit{cntr}-1]$ 所组成子串的长度$l_2$ 为 $s[\textit{cntr}]$ 到该重串左半原串末字符所组成子串的长度。此时可以给出某个长度为 $2l 2(l_1 l_2) 2(|u| - \textit{cntr})$ 的子串是重串的充分必要条件。为此定义两个关键量$k_1$满足 $u[\textit{cntr} - k_1 \dots \textit{cntr} - 1] u[|u| - k_1 \dots |u| - 1]$ 的最大整数即左半段内部后缀能向左延伸匹配多长$k_2$满足 $u[\textit{cntr} \dots \textit{cntr} k_2 - 1] v[0 \dots k_2 - 1]$ 的最大整数即跨过分界点能向右延伸匹配多长。则对于任意满足 $l_1 \le k_1$、$l_2 \le k_2$ 的二元组 $(l_1, l_2)$都能恰好找到一个与之对应的重串。总结流程固定一个 $\textit{cntr}$此时要找的重串长度均为 $2l 2(|u| - \textit{cntr})$但仍可能有多个重串取决于 $l_1$ 与 $l_2$ 的取值计算上述 $k_1$、$k_2$则所有符合条件的重串满足约束 $$ \begin{align} l_1 l_2 l |u| - \textit{cntr} \ l_1 \le k_1, \ l_2 \le k_2. \ \end{align} $$用 Z 函数 O(1) 求 k1 与 k2剩下的问题是如何快速计算 $k_1$ 与 $k_2$。借助Z 函数即扩展 KMP / exKMP见 docs/string/z-func.md可以做到 $O(1)$ 查询计算 $k_1$只需计算 $\overline{u}$左部的反串的 Z 函数。因为 $u[\textit{cntr} - k_1 \dots \textit{cntr} - 1]$ 与 $u[|u| - k_1 \dots |u| - 1]$ 的匹配在反串视角下恰好对应$u[|u|-\textit{cntr}]$ 位置处的 Z 值即 $z_1[|u|-\textit{cntr}]$。计算 $k_2$只需计算 $v # u$ 的 Z 函数其中 $#$ 是一个在 $u$、$v$ 中都没有出现过的分隔字符。因为 $u[\textit{cntr} \dots \textit{cntr}k_2-1]$ 与 $v[0 \dots k_2-1]$ 的匹配等价于 $u$ 中位置 $\textit{cntr}$ 的后缀与模式串 $v$ 的最长公共前缀这正是 $z_2[|v|1\textit{cntr}]$ 的含义。Z 函数 $z[i]$ 定义为 $s$ 与其从 $i$ 开始的后缀的最长公共前缀长度$z[0]0$其线性时间求法依赖匹配段Z-box的维护总复杂度 $O(n)$。由于分治的每一层都只需对 $u$、$v$ 及其反串各做一次 $O(n)$ 的 Z 函数计算整层合并代价是线性的。右偏重串完全对称的处理计算右偏重串的方法与左偏几乎一致只是镜像翻转。考虑该重串第一个落入 $u$ 的字符即 $s[|u|-1]$它一定与 $v$ 中的某个字符一致记这个字符在 $v$ 中的位置为 $\textit{cntr}$此处以 $v$ 内下标计。对称地定义$k_1$满足 $v[\textit{cntr} - k_1 1 \dots \textit{cntr}] u[|u| - k_1 \dots |u| - 1]$ 的最大整数$k_2$满足 $v[\textit{cntr} 1 \dots \textit{cntr} k_2] v[0 \dots k_2 - 1]$ 的最大整数。它们可以分别通过计算 $\overline{u} # \overline{v}$ 和 $v$ 的 Z 函数得出。然后枚举 $\textit{cntr}$用相仿的方法寻找右偏重串即可。完整实现与复杂度分析四元组输出形式Main–Lorentz 算法以四元组 $(\textit{cntr}, l, k_1, k_2)$ 的形式给出所有重串。如果你只需要计算重串的数量或者只需要找到最长的一个重串这个四元组提供的信息已经足够无需显式展开。由 主定理 (Master Theorem) 可得其时间复杂度。分治递推式为 $T(n) 2T(n/2) O(n)$每层做常数次线性 Z 函数计算对应主定理 $a2, b2, \log_b a 1$ 与 $f(n)\Theta(n)$ 的第三种情形故总复杂度为 $O(n \log n)$。⚠️ 注意如果你想通过四元组展开得到所有重串的起始位置与终止位置最坏时间复杂度会达到 $O(n^2)$因为重串本身可能就有 $O(n^2)$ 个。下面给出的程序正是实现了这一点将所有重串的起止位置存入repetitions容器。C 代码含详细注释#include bits/stdc.h using namespace std; // 线性时间 Z 函数z[i] s 与 s 从 i 开始的后缀的最长公共前缀长度 vectorint z_function(string const s) { int n s.size(); vectorint z(n); for (int i 1, l 0, r 0; i n; i) { if (i r) z[i] min(r - i 1, z[i - l]); // 复用 Z-box 内已有信息 while (i z[i] n s[z[i]] s[i z[i]]) z[i]; // 暴力扩展 if (i z[i] - 1 r) { l i; r i z[i] - 1; // 更新最右匹配段 [l, r] } } return z; } // 越界安全的 Z 值访问下标越界时视为 0 int get_z(vectorint const z, int i) { if (0 i i (int)z.size()) return z[i]; else return 0; } vectorpairint, int repetitions; // 存储所有重串的 [起始, 终止] 下标 // 将由四元组 (cntr, l, k1, k2) 表示的所有重串展开为起止区间 // shift: 当前子串在原始字符串中的偏移量 // left: 是否为左偏重串 void convert_to_repetitions(int shift, bool left, int cntr, int l, int k1, int k2) { // l1 的可取范围为 [max(1, l - k2), min(l, k1)] for (int l1 max(1, l - k2); l1 min(l, k1); l1) { if (left l1 l) break; // 左偏重串不允许 l1 l否则不跨过分界点 int l2 l - l1; // 由 l1 l2 l 决定 int pos shift (left ? cntr - l1 : cntr - l - l1 1); repetitions.emplace_back(pos, pos 2 * l - 1); } } // 在子串 s 上寻找所有重串shift 是该子串在原始字符串中的偏移量 void find_repetitions(string s, int shift 0) { int n s.size(); if (n 1) return; // 长度为 1 不可能有重串 int nu n / 2; // 左部长度 int nv n - nu; // 右部长度 string u s.substr(0, nu); string v s.substr(nu); string ru(u.rbegin(), u.rend()); // u 的反串 string rv(v.rbegin(), v.rend()); // v 的反串 // 分治分别处理完全位于左部、完全位于右部的重串 find_repetitions(u, shift); find_repetitions(v, shift nu); // 四次 Z 函数计算用于 O(1) 查询 k1、k2 vectorint z1 z_function(ru); // 左偏 k1 vectorint z2 z_function(v # u); // 左偏 k2 vectorint z3 z_function(ru # rv); // 右偏 k1 vectorint z4 z_function(v); // 右偏 k2 for (int cntr 0; cntr n; cntr) { int l, k1, k2; if (cntr nu) { // 左偏重串中间字符在 u 中 l nu - cntr; k1 get_z(z1, nu - cntr); k2 get_z(z2, nv 1 cntr); } else { // 右偏重串中间字符在 v 中 l cntr - nu 1; k1 get_z(z3, nu 1 nv - 1 - (cntr - nu)); k2 get_z(z4, (cntr - nu) 1); } // 存在满足 l1 l2 l, l1 k1, l2 k2 的分配才可能产生重串 if (k1 k2 l) convert_to_repetitions(shift, cntr nu, cntr, l, k1, k2); } }对上述实现做几点深入说明z_function的线性性外层循环线性扫描内层while每次都会使最右匹配端点 $r$ 至少后移一位而 $r n$故内层总执行次数为 $O(n)$总复杂度 $O(n)$。具体原理见 Z 函数详解。convert_to_repetitions的约束l1从 $\max(1, l-k_2)$ 枚举到 $\min(l, k_1)$正是约束 $l_1 \le k_1$、$l_2 l - l_1 \le k_2$ 的直接翻译left l1 l的跳出保证左偏重串必然跨过分界点。k1 k2 l的预判这是对解存在性的快速筛选。因为 $l_1 l_2 l$ 且 $l_1 \le k_1, l_2 \le k_2$ 有整数解当且仅当 $k_1 k_2 \ge l$结合 $l_1 \ge 1$ 的边界。分隔符#的选择必须保证该字符不出现在 $u$、$v$ 中否则会人为制造出跨越分隔符的虚假匹配。对于仅含小写字母的题目输入任意非小写字母字符如#、$均可。空间复杂度递归深度为 $O(\log n)$每层产生 4 个长度为 $O(n)$ 的 Z 数组每层合计 $O(n)$若及时释放可做到总空间 $O(n)$repetitions在最坏情形显式展开所有重串下可达到 $O(n^2)$ 规模。应用场景与扩展讨论Main–Lorentz 算法适用于以下典型场景统计重串数量只累加四元组即可复杂度 $O(n \log n)$无需展开寻找最长重串对每个四元组最长者可取 $l_1 \min(l, k_1)$ 对应的展开扫描一遍即可输出全部重串区间调用find_repetitions(s)后遍历全局容器repetitions如本页实现所示最坏 $O(n^2)$。值得注意的边界与细节交叉重串的判定依赖中间字符落在哪一半因此分界点 $|u|$ 的取法向下取整 vs 向上取整会影响实现细节但只要递归时左右部分长度之和恒等于当前串长正确性不受影响该算法与后缀数组 / 后缀自动机等传统字符串工具不同它不依赖字符集大小仅需字符串相等性比较对任意字符集包括整数序列都适用若题目只要求 $O(n \log n)$ 求本原重串或使用 Crochemore 三元组计数可在此基础上改造convert_to_repetitions按循环节合并输出。小结Main–Lorentz 算法是一个分治 Z 函数的经典组合分治负责把交叉重串问题拆解为可枚举的左偏/右偏子问题Z 函数负责把每个 $\textit{cntr}$ 处的 $k_1, k_2$ 查询压到 $O(1)$。整个算法的精髓在于用四元组压缩重串从而在 $O(n \log n)$ 时间内完成本需要 $O(n^2)$ 才能显式列举的工作。本文所对应的原始文档位于 docs/string/main-lorentz.md其依赖的基础知识包括 Z 函数扩展 KMP 与 主定理关于字符串的基础概念子串、后缀、前缀、字符集等可参考 docs/string/basic.md。建议读者在动手实现前先以 $\tt acababaee$ 与 $\tt abaaba$ 两个例子手工推演一遍左偏重串的 $k_1/k_2$ 计算再对照代码验证输出区间。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考