Main-Lorentz 算法

重串

定义

给定一个长度为 的字符串 。

我们将一个字符串连续写两遍所产生的新字符串称为 重串 (tandem repetition)。下文中，为了表述精准，我们将被重复的这个字符串称为原串。换言之，一个重串等价于一对下标 ，其使得 是两个相同字符串拼接而成的。

你的目标是找出给定的字符串 中所有的重串。或者，解决一个较为简单的问题：找到字符串 中任意重串或者最长的一个重串。

下文的算法由 Michael Main 和 Richard J. Lorentz 在 1982 年提出。

声明：

下文所有的字符串下标从 0 开始。

下文中，记 为 的反串。如 。

解释

考虑字符串 ，这个字符串包括三个重串，分别是：

下面是另一个例子，考虑字符串 ，这个字符串只有两个重串：

重串的个数

一个长度为 的字符串可能有高达 个重串，一个显然的例子就是 个字母全部相同的字符串，这种情况下，只要其子串长度为偶数，这个子串就是重串。多数情况下，一个周期比较小的周期字符串会有很多重串。

但这并不影响我们在 的时间内计算出重串数量。因为这个算法通过某种压缩形式来表达一个重串，使得我们可以将多个重串压缩为一个。

这里有一些关于重串数量的有趣结论：

• 如果一个重串的原串不是重串，则我们称这个重串为 本原重串 (primitive repetition)。可以证明，本原重串最多有 个。
• 如果我们把一个重串用 Crochemore 三元组 进行压缩，其中 是重串的起始位置， 是该重串某个循环节的长度（注意不是原串长度！）， 为这个循环节重复的次数。则某字符串的所有重串可以被 个 Crochemore 三元组表示。
• Fibonacci 字符串定义如下：

可以发现 Fibonacci 字符串具有高度的周期性。对于长度为 的 Fibonacci 字符串 ，即使用 Crochemore 三元组压缩，也有 个三元组。其本原重串的数量也有 个。

Main-Lorentz 算法

解释

Main-Lorentz 算法的核心思想是 分治。

这个算法将字符串分为左、右两部分，首先计算完全处于字符串左部（或右部）的重串数量，然后计算起始位置在左部，终止在右部的重串数量。（下文中，我们将这种重串称为 交叉重串）

计算交叉重串的数量是 Main-Lorentz 算法的关键点，我们将在下文详细探讨。

过程

寻找交叉重串

我们记某字符串的左部为 ，右部为 。则 ，且 的长度大约等于 长度的一半。

对于任意一个重串，我们考虑其中间字符。此处我们将一个重串右半边的第一个字符称为其中间字符，换言之，若 为重串，则其中间字符为 。如果一个重串的中间字符在 中，则称这个重串 左偏 (left)，反之则称其 右偏 (right)。

接下来，我们将会探讨如何找到所有的左偏重串。

我们记一个左边重串的长度为 。考虑该重串第一个落入 的字符（即 ），这个字符一定与 中的某个字符 一致。

我们考虑固定 ，并找到所有符合条件的重串。举个例子：对于字符串 （这个 是用于分辨左右两部分的），固定 ，则我们可以发现重串 符合要求。

显然，我们一旦固定了 ，那我们同时也固定了 的取值。我们一旦知道如何找到所有重串，我们就可以从 到 枚举 的取值，然后找到所有符合条件的重串。

左偏重串的判定

即使固定 后，仍然可能会有多个符合条件的重串，我们怎么找到所有符合条件的重串呢？

我们再来举一个例子，对于字符串 中的重串 ，我们记 为该重串的首字符到 所组成的子串的长度，记 为 到该重串左边原串的末字符所组成的子串的长度。

于是，我们可以给出某个长度为 的子串是重串的 充分必要条件：

记 为满足 的最大整数，记 为满足 的最大整数。则对于任意满足 ， 的二元组 ，我们都能恰好找到一个与之对应的重串。

总结一下，即有：

• 固定一个 。
• 那么我们此时要找的重串长度均为 。此时可能仍有多个符合条件的重串，取决于 与 的取值。
• 计算上文提到的 ，。
• 则所有符合条件的重串符合条件：

接下来，只需要考虑如何快速算出 与 了。借助

Z 函数，我们可以 计算它们：

• 计算 ：只需计算 的 Z 函数即可。
• 计算 ：只需计算 的 Z 函数即可，其中 是一个 ， 中均没有的字符。

右偏重串

计算右偏重串的方法与计算左偏重串的方法几乎一致。考虑该重串第一个落入 的字符（即 ），则其一定与 中的某个字符一致，记这个字符在 中的位置为 。

令 为满足 的最大整数， 为满足 的最大整数。则我们可以分别通过计算 和 的 Z 函数来得出 与 。

枚举 ，用相仿的方法寻找右偏重串即可。

实现

Main-Lorentz 算法以四元组 的形式给出所有重串。如果你只需要计算重串的数量，或者只需要找到最长的一个重串，这个四元组给的信息是足够的。由

主定理 可得，Main-Lorentz 算法的时间复杂度为 。

请注意，如果你想通过这些四元组来找到所有重串的起始位置与终止位置，则最坏时间复杂度会达到 。我们在下面的程序中实现了这一点，将所有重串的起始位置与终止位置存于 repetitions 中。

本页面主要译自博文 Поиск всех тандемных повторов в строке. Алгоритм Мейна-Лоренца 与其英文翻译版 Finding repetitions。其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0。