跳转至

Main–Lorentz 算法

重串

定義

給定一個長度為 \(n\) 的字符串 \(s\)。

我們將一個字符串連續寫兩遍所產生的新字符串稱為 重串 (tandem repetition)。下文中，為了表述精準，我們將被重複的這個字符串稱為原串。換言之，一個重串等價於一對下標 \((i, j)\)，其使得 \(s[i \dots j]\) 是兩個相同字符串拼接而成的。

你的目標是找出給定的字符串 \(s\) 中所有的重串。或者，解決一個較為簡單的問題：找到字符串 \(s\) 中任意重串或者最長的一個重串。

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

聲明：

下文所有的字符串下標從 0 開始。

下文中，記 \(\overline{s}\) 為 \(s\) 的反串。如 \(\overline{\tt abc} = \tt cba\)。

解釋

考慮字符串 \(\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\)

重串的個數

一個長度為 \(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)\) 個。

Main–Lorentz 算法

解釋

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

這個算法將字符串分為左、右兩部分，首先計算完全處於字符串左部（或右部）的重串數量，然後計算起始位置在左部，終止在右部的重串數量。（下文中，我們將這種重串稱為 交叉重串）

計算交叉重串的數量是 Main–Lorentz 算法的關鍵點，我們將在下文詳細探討。

過程

尋找交叉重串

我們記某字符串的左部為 \(u\)，右部為 \(v\)。則 \(s = u + v\)，且 \(u, v\) 的長度大約等於 \(s\) 長度的一半。

對於任意一個重串，我們考慮其中間字符。此處我們將一個重串右半邊的第一個字符稱為其中間字符，換言之，若 \(s[i...j]\) 為重串，則其中間字符為 \(s[(i + j + 1)/2]\)。如果一個重串的中間字符在 \(u\) 中，則稱這個重串 左偏 (left)，反之則稱其 右偏 (right)。

接下來，我們將會探討如何找到所有的左偏重串。

我們記一個左邊重串的長度為 \(2l\)。考慮該重串第一個落入 \(v\) 的字符（即 \(s[|u|]\)），這個字符一定與 \(u\) 中的某個字符 \(u[\textit{cntr}]\) 一致。

我們考慮固定 \(\textit{cntr}\)，並找到所有符合條件的重串。舉個例子：對於字符串 \(\tt c \; \underset{\textit{cntr}}{a} \; c \; | \; a \; d \; a\)（這個 \(\tt |\) 是用於分辨左右兩部分的），固定 \(cntr = 1\)，則我們可以發現重串 \(\tt caca\) 符合要求。

顯然，我們一旦固定了 \(\textit{cntr}\)，那我們同時也固定了 \(l\) 的取值。我們一旦知道如何找到所有重串，我們就可以從 \(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 \leq k_1\)，\(l_2 \leq 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} \]

接下來，只需要考慮如何快速算出 \(k_1\) 與 \(k_2\) 了。藉助 Z 函數，我們可以 \(O(1)\) 計算它們：

  • 計算 \(k_1\)：只需計算 \(\overline{u}\) 的 Z 函數即可。
  • 計算 \(k_2\)：只需計算 \(v + \# + u\) 的 Z 函數即可，其中 \(\#\) 是一個 \(u\)，\(v\) 中均沒有的字符。

右偏重串

計算右偏重串的方法與計算左偏重串的方法幾乎一致。考慮該重串第一個落入 \(u\) 的字符（即 \(s[|u| - 1]\)），則其一定與 \(v\) 中的某個字符一致，記這個字符在 \(v\) 中的位置為 \(\textit{cntr}\)。

令 \(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 函數來得出 \(k_1\) 與 \(k_2\)。

枚舉 \(\textit{cntr}\)，用相仿的方法尋找右偏重串即可。

實現

Main–Lorentz 算法以四元組 \((\textit{cntr}, l, k_1, k_2)\) 的形式給出所有重串。如果你只需要計算重串的數量，或者只需要找到最長的一個重串，這個四元組給的信息是足夠的。由 主定理 可得，Main–Lorentz 算法的時間複雜度為 \(O(n \log n)\)。

請注意，如果你想通過這些四元組來找到所有重串的起始位置與終止位置，則最壞時間複雜度會達到 \(O(n^2)\)。我們在下面的程序中實現了這一點，將所有重串的起始位置與終止位置存於 repetitions 中。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
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);
  }
}

本頁面主要譯自博文 Поиск всех тандемных повторов в строке. Алгоритм Мейна-Лоренца 與其英文翻譯版 Finding repetitions。其中俄文版版權協議為 Public Domain + Leave a Link；英文版版權協議為 CC-BY-SA 4.0。

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用