企业官网建设流程全解析

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$。

你的目标通常是两类问题：

1. 找出字符串 $s$ 中所有的重串；
2. 较简单的问题：找到 $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)$ 时间内计算出重串数量，关键在于：算法通过某种压缩形式来表达重串，使得多个重串可以被合并为一个。关于重串数量，有以下三个有趣结论：

1. 如果某个重串的原串本身不是重串，则称它为本原重串（primitive repetition）。可以证明，本原重串最多有 $O(n \log n)$ 个。
2. 若将重串用Crochemore 三元组$(i, p, r)$ 压缩——其中 $i$ 是重串的起始位置，$p$ 是某个循环节的长度（注意：不是原串长度！），$r$ 为该循环节重复的次数——则一个字符串的所有重串可以被 $O(n \log n)$ 个 Crochemore 三元组表示。
3. 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 算法的核心思想是分治，与归并排序有着相似的递归骨架：

1. 将字符串划分为左部与右部；
2. 递归计算完全处于左部（或右部）的重串数量；
3. 计算起始位置在左部、终止位置在右部的重串数量——这类重串在下文中称为交叉重串（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[(i+j+1)/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)$，都能恰好找到一个与之对应的重串。

总结流程：

1. 固定一个 $\textit{cntr}$；
2. 此时要找的重串长度均为 $2l = 2(|u| - \textit{cntr})$，但仍可能有多个重串，取决于 $l_1$ 与 $l_2$ 的取值；
3. 计算上述 $k_1$、$k_2$；
4. 则所有符合条件的重串满足约束： $$ \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 函数计算），对应主定理 $a=2, b=2, \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 开始的后缀的最长公共前缀长度 vector<int> z_function(string const& s) { int n = s.size(); vector<int> 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(vector<int> const& z, int i) { if (0 <= i && i < (int)z.size()) return z[i]; else return 0; } vector<pair<int, 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 vector<int> z1 = z_function(ru); // 左偏 k1 vector<int> z2 = z_function(v + '#' + u); // 左偏 k2 vector<int> z3 = z_function(ru + '#' + rv); // 右偏 k1 vector<int> 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 算法适用于以下典型场景：

1. 统计重串数量：只累加四元组即可，复杂度 $O(n \log n)$，无需展开；
2. 寻找最长重串：对每个四元组，最长者可取 $l_1 = \min(l, k_1)$ 对应的展开，扫描一遍即可；
3. 输出全部重串区间：调用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