【翻译】寻找重串与 Main-Lorentz 算法

2022-03-25 15:27:10

注：本文翻译自 Поиск всех тандемных повторов в строке. Алгоритм Мейна-Лоренца 及其英文翻译版 Finding repetitions，转载时请标注出原文与本文的出处。

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

我们将一个字符串连续写两遍所产生的新字符串称为 重串 (repetition)。下文中，为了表述精准，我们将被重复的这个字符串称为原串。

换言之，一个重串等价于一对下标 ( i , j ) (i, j) (i,j)，其使得 s [ i … j ] s[i \dots j] s[i…j] 是两个相同字符串拼接而成的。

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

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

声明：

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

下文中，记 s ‾ \overline{s} s 为 s s s 的反串。如 a b c ‾ = c b a \overline{\tt abc} = \tt cba abc=cba。

例子

考虑字符串 a c a b a b a e e \tt acababaee acababaee，这个字符串包括三个重串，分别是：

s [ 2 … 5 ] = a b a b s[2 \dots 5] = \tt abab s[2…5]=abab
s [ 3 … 6 ] = b a b a s[3 \dots 6] = \tt baba s[3…6]=baba
s [ 7 … 8 ] = e e s[7 \dots 8] = \tt ee s[7…8]=ee

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

s [ 0 … 5 ] = a b a a b a s[0 \dots 5] = \tt abaaba s[0…5]=abaaba
s [ 2 … 3 ] = a a s[2 \dots 3] = \tt aa s[2…3]=aa

重串的个数

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

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

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

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

t 0 = a , t 1 = b , t i = t i − 1 + t i − 2 , \begin{aligned} t_0 &= a, \\ t_1 &= b, \\ t_i &= t_{i-1} + t_{i-2}, \end{aligned} t0t1ti=a,=b,=ti−1+ti−2,

可以发现 Fibonacci 字符串具有高度的周期性。对于长度为 f i f_i fi 的 Fibonacci 字符串 t i t_i ti，即使用 Crochemore 三元组压缩，也有 O ( f i log ⁡ f i ) O(f_i \log f_i) O(filogfi) 个三元组。其本原重串的数量也有 O ( f i log ⁡ f i ) O(f_i \log f_i) O(filogfi) 个。

Main-Lorentz 算法

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

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

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

寻找交叉重串

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

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

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

我们记一个左边重串的长度为 2 l 2l 2l。考虑该重串第一个落入 v v v 的字符（即 s [ ∣ u ∣ ] s[|u|] s[∣u∣]），这个字符一定与 u u u 中的某个字符 u [ c n t r ] u[cntr] u[cntr] 一致。

我们考虑固定 c n t r cntr cntr，并找到所有符合条件的重串。举个例子：对于字符串 c a c n t r c ∣ a d a \tt c \; \underset{\rm cntr}{a} \; c \; | \; a \; d \; a ccntrac∣ada（这个 ∣ \tt | ∣ 是用于分辨左右两部分的），固定 c n t r = 1 cntr = 1 cntr=1，则我们可以发现重串 c a c a \tt caca caca 符合要求。

显然，我们一旦固定了 c n t r cntr cntr，那我们同时也固定了 l l l 的可能的取值。我们一旦知道如何找到所有重串，我们就可以从 0 0 0 到 ∣ u ∣ − 1 |u| - 1 ∣u∣−1 枚举 c n t r cntr cntr 的取值，然后找到所有符合条件的重串。

左偏重串的判定

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

我们再来举一个例子，对于字符串 a b c a b c a c \tt abcabcac abcabcac 中的重串 a ⏞ l 1 b c n t r c ⏞ l 2 a ⏞ l 1 ∣ b c ⏞ l 2 \overbrace{\tt a}^{l_1} \overbrace{\underset{cntr}{\tt b} \tt c}^{l_2} \overbrace{\tt a}^{l_1} \; | \; \overbrace{\tt b \; \tt c}^{l_2} a l1cntrbc l2a l1∣bc l2，我们记 l 1 l_1 l1 为该重串的首字符到 s [ c n t r − 1 ] s[cntr - 1] s[cntr−1] 所组成的子串的长度，记 l 2 l_2 l2 为 s [ c n t r ] s[cntr] s[cntr] 到该重串左边原串的末字符所组成的子串的长度。

我们可以给出满足条件，且长度为 2 l = 2 ( l 1 + l 2 ) = 2 ( ∣ u ∣ − c n t r ) 2l = 2(l_1 + l_2) = 2(|u| - cntr) 2l=2(l1+l2)=2(∣u∣−cntr) 的重串的 充分必要条件：

记 k 1 k_1 k1 为满足 u [ c n t r − k 1 … c n t r − 1 ] = u [ ∣ u ∣ − k 1 … ∣ u ∣ − 1 ] u[cntr - k_1 \dots cntr - 1] = u[|u| - k_1 \dots |u| - 1] u[cntr−k1…cntr−1]=u[∣u∣−k1…∣u∣−1] 的最大整数，记 k 2 k_2 k2 为满足 u [ c n t r … c n t r + k 2 − 1 ] = v [ 0 … k 2 − 1 ] u[cntr \dots cntr + k_2 - 1] = v[0 \dots k_2 - 1] u[cntr…cntr+k2−1]=v[0…k2−1] 的最大整数。

则对于任意满足 0 ≤ l 1 ≤ k 1 0 \leq l_1 \leq k_1 0≤l1≤k1， 0 ≤ l 2 ≤ k 2 0 \leq l_2 \leq k_2 0≤l2≤k2 的二元组 ( l 1 , l 2 ) (l_1, l_2) (l1,l2)，我们都能恰好找到一个与之对应的重串。

总结一下，即有：

固定一个 c n t r cntr cntr。
那么我们此时要找的重串长度均为 2 l = 2 ( ∣ u ∣ − c n t r ) 2l = 2(|u| - cntr) 2l=2(∣u∣−cntr)。此时可能仍有多个符合条件的重串，取决于 l 1 l_1 l1 与 l 2 l_2 l2 的取值。
计算上文提到的 k 1 k_1 k1， k 2 k_2 k2。
则所有符合条件的重串符合条件：
l 1 + l 2 = l = ∣ u ∣ − c n t r l 1 ≤ k 1 , l 2 ≤ k 2 . \begin{aligned} l_1 + l_2 &= l = |u| - cntr \\ l_1 &\le k_1, \\ l_2 &\le k_2. \\ \end{aligned} l1+l2l1l2=l=∣u∣−cntr≤k1,≤k2.

接下来，只需要考虑如何快速算出 k 1 k_1 k1 与 k 2 k_2 k2 了。借助 Z 函数，我们可以 O ( 1 ) O(1) O(1) 计算它们：

计算 k 1 k_1 k1：只需计算 u ‾ \overline{u} u 的 Z 函数即可。
计算 k 2 k_2 k2：只需计算 v + # + u v + \# + u v+#+u 的 Z 函数即可，其中 # \# # 是一个 u u u， v v v 中均没有的字符。

右偏重串

计算右偏重串的方法与计算左偏重串的方法几乎一致。考虑该重串第一个落入 u u u 的字符（即 s [ ∣ u ∣ − 1 ] s[|u| - 1] s[∣u∣−1]），则其一定与 v v v 中的某个字符一致，记这个字符在 v v v 中的位置为 c n t r cntr cntr。

令 k 1 k_1 k1 为满足 v [ c n t r − k 1 + 1 … c n t r ] = u [ ∣ u ∣ − k 1 … ∣ u ∣ − 1 ] v[cntr - k_1 + 1 \dots cntr] = u[|u| - k_1 \dots |u| - 1] v[cntr−k1+1…cntr]=u[∣u∣−k1…∣u∣−1] 的最大整数， k 2 k_2 k2 为满足 v [ c n t r + 1 … c n t r + k 2 ] = v [ 0 … k 2 − 1 ] v[cntr + 1 \dots cntr + k_2] = v[0 \dots k_2 - 1] v[cntr+1…cntr+k2]=v[0…k2−1] 的最大整数。则我们可以分别通过计算 u ‾ + # + v ‾ \overline{u} + \# + \overline{v} u+#+v 和 v v v 的 Z 函数来得出 k 1 k_1 k1 与 k 2 k_2 k2。

枚举 c n t r cntr cntr，用相仿的条件寻找右偏重串即可。

算法实现

Main-Lorentz 算法以四元组 ( c n t r , l , k 1 , k 2 ) (cntr, l, k_1, k_2) (cntr,l,k1,k2) 的形式给出所有重串。如果你只需要计算重串的数量，或者只需要找到最长的一个重串，这个四元组给的信息是足够的。Main-Lorentz 算法的时间复杂度为 O ( n log ⁡ n ) O(n \log n) O(nlogn)。

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

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]);
        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;
        }
    }
    return z;
}

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;

void convert_to_repetitions(int shift, bool left, int cntr, int l, int k1, int k2) {
    for (int l1 = max(1, l - k2); l1 <= min(l, k1); l1++) {
        if (left && l1 == l) break;
        int l2 = l - l1;
        int pos = shift + (left ? cntr - l1 : cntr - l - l1 + 1);
        repetitions.emplace_back(pos, pos + 2*l - 1);
    }
}

void find_repetitions(string s, int shift = 0) {
    int n = s.size();
    if (n == 1)
        return;

    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());
    string rv(v.rbegin(), v.rend());

    find_repetitions(u, shift);
    find_repetitions(v, shift + nu);

    vector<int> z1 = z_function(ru);
    vector<int> z2 = z_function(v + '#' + u);
    vector<int> z3 = z_function(ru + '#' + rv);
    vector<int> z4 = z_function(v);

    for (int cntr = 0; cntr < n; cntr++) {
        int l, k1, k2;
        if (cntr < nu) {
            l = nu - cntr;
            k1 = get_z(z1, nu - cntr);
            k2 = get_z(z2, nv + 1 + cntr);
        } else {
            l = cntr - nu + 1;
            k1 = get_z(z3, nu + 1 + nv - 1 - (cntr - nu));
            k2 = get_z(z4, (cntr - nu) + 1);
        }
        if (k1 + k2 >= l)
            convert_to_repetitions(shift, cntr < nu, cntr, l, k1, k2);
    }
}

此处我省略了一句：“There is even the concept, that describes groups of periodic substrings with tuples of size four. It has been proven that we the number of such groups is at most linear with respect to the string length.”。 ↩︎

码农公寓