Skip to content

Main–Lorentz Algorithm

Tandem Repetitions

Definition

Given a string \(s\) of length \(n\).

A string formed by writing the same string twice consecutively is called a tandem repetition. In the following, for precise expression, we refer to the repeated string as the original string. In other words, a tandem repetition corresponds to a pair of indices \((i, j)\) such that \(s[i \dots j]\) is the concatenation of two identical strings.

Your goal is to find all tandem repetitions in the given string \(s\). Alternatively, solve a simpler problem: find any tandem repetition or the longest tandem repetition in \(s\).

The algorithm described below was proposed by Michael Main and Richard J. Lorentz in 1982.

Conventions

All string indices below start from \(0\).

In the following, let \(\overline{s}\) denote the reverse of \(s\). For example, \(\overline{\tt abc} = \tt cba\).

Explanation

Consider the string \(\tt acababaee\), which contains three tandem repetitions:

  • \(s[2 \dots 5] = \tt abab\)
  • \(s[3 \dots 6] = \tt baba\)
  • \(s[7 \dots 8] = \tt ee\)

Here is another example, consider the string \(\tt abaaba\), which has only two tandem repetitions:

  • \(s[0 \dots 5] = \tt abaaba\)
  • \(s[2 \dots 3] = \tt aa\)

Number of Tandem Repetitions

A string of length \(n\) can have up to \(O(n^2)\) tandem repetitions. An obvious example is a string consisting of \(n\) identical characters, where any substring of even length is a tandem repetition. In many cases, a periodic string with a small period will have many tandem repetitions.

However, this does not prevent us from computing the number of tandem repetitions in \(O(n \log n)\) time. This algorithm expresses tandem repetitions in a compressed form, allowing multiple tandem repetitions to be compressed into one.

Here are some interesting conclusions about the number of tandem repetitions:

  • If the original string of a tandem repetition is not itself a tandem repetition, we call it a primitive repetition. It can be proven that there are at most \(O(n \log n)\) primitive repetitions.
  • If we compress a tandem repetition using a Crochemore triple \((i, p, r)\), where \(i\) is the starting position of the tandem repetition, \(p\) is the length of some period of the tandem repetition (note: not the length of the original string!), and \(r\) is the number of repetitions of this period. Then all tandem repetitions of a string can be represented by \(O(n \log n)\) Crochemore triples.
  • The Fibonacci string is defined as:
\[ \begin{align} t_0 &= a, \\ t_1 &= b, \\ t_i &= t_{i-1} + t_{i-2}, \end{align} \]

It can be observed that Fibonacci strings have high periodicity. For the Fibonacci string \(t_i\) of length \(f_i\), even when compressed using Crochemore triples, there are \(O(f_i \log f_i)\) triples. The number of primitive repetitions is also \(O(f_i \log f_i)\).

Main–Lorentz Algorithm

Explanation

The core idea of the Main–Lorentz algorithm is divide and conquer.

The algorithm splits the string into left and right parts. First, it counts the number of tandem repetitions entirely within the left (or right) part. Then it counts the number of tandem repetitions that start in the left part and end in the right part (referred to as crossing tandem repetitions below).

Calculating the number of crossing tandem repetitions is the key point of the Main–Lorentz algorithm, which we will discuss in detail below.

Procedure

Finding Crossing Tandem Repetitions

Let the left part of the string be \(u\) and the right part be \(v\). Then \(s = u + v\), and the lengths of \(u\) and \(v\) are approximately half the length of \(s\).

For any tandem repetition, consider its middle character. Here, we define the middle character as the first character of the right half of the tandem repetition. In other words, if \(s[i...j]\) is a tandem repetition, its middle character is \(s[(i + j + 1)/2]\). If the middle character of a tandem repetition lies in \(u\), we call it left-biased; otherwise, we call it right-biased.

Next, we will discuss how to find all left-biased tandem repetitions.

Let the length of a left-biased tandem repetition be \(2l\). Consider the first character of this tandem repetition that falls into \(v\) (i.e., \(s[|u|]\)). This character must match some character \(u[\textit{cntr}]\) in \(u\).

We consider fixing \(\textit{cntr}\) and finding all qualifying tandem repetitions. For example: for the string \(\tt c \; \underset{\textit{cntr}}{a} \; c \; | \; a \; d \; a\) (the \(\tt |\) separates the left and right parts), fixing \(cntr = 1\), we find the tandem repetition \(\tt caca\) satisfies the condition.

Clearly, once \(\textit{cntr}\) is fixed, the value of \(l\) is also fixed. Once we know how to find all tandem repetitions, we can enumerate \(\textit{cntr}\) from \(0\) to \(|u| - 1\) and find all qualifying tandem repetitions.

Determining Left-Biased Tandem Repetitions

Even after fixing \(\textit{cntr}\), there may still be multiple qualifying tandem repetitions. How do we find all of them?

Let's take another example. For the tandem repetition \(\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}\) in the string \(\tt abcabcac\), let \(l_1\) be the length of the substring from the first character of the tandem repetition to \(s[\textit{cntr} - 1]\), and let \(l_2\) be the length of the substring from \(s[\textit{cntr}]\) to the last character of the left original string of the tandem repetition.

Thus, we can give the necessary and sufficient condition for a substring of length \(2l = 2(l_1 + l_2) = 2(|u| - \textit{cntr})\) to be a tandem repetition:

Let \(k_1\) be the largest integer such that \(u[\textit{cntr} - k_1 \dots \textit{cntr} - 1] = u[|u| - k_1 \dots |u| - 1]\), and let \(k_2\) be the largest integer such that \(u[\textit{cntr} \dots \textit{cntr} + k_2 - 1] = v[0 \dots k_2 - 1]\). Then for any pair \((l_1, l_2)\) satisfying \(l_1 \leq k_1\) and \(l_2 \leq k_2\), we can find exactly one corresponding tandem repetition.

To summarize:

  • Fix a \(\textit{cntr}\).
  • Then the length of the tandem repetitions we are looking for is \(2l = 2(|u| - \textit{cntr})\). There may still be multiple qualifying tandem repetitions, depending on the values of \(l_1\) and \(l_2\).
  • Compute \(k_1\) and \(k_2\) as mentioned above.
  • Then all qualifying tandem repetitions satisfy:
\[ \begin{align} l_1 + l_2 &= l = |u| - \textit{cntr} \\ l_1 &\le k_1, \\ l_2 &\le k_2. \\ \end{align} \]

Next, we only need to consider how to compute \(k_1\) and \(k_2\) quickly. Using the Z-function, we can compute them in \(O(1)\):

  • Compute \(k_1\): simply compute the Z-function of \(\overline{u}\).
  • Compute \(k_2\): simply compute the Z-function of \(v + \# + u\), where \(\#\) is a character not present in \(u\) or \(v\).

Right-Biased Tandem Repetitions

The method for computing right-biased tandem repetitions is almost identical to that for left-biased ones. Consider the first character of the tandem repetition that falls into \(u\) (i.e., \(s[|u| - 1]\)). It must match some character in \(v\); denote its position in \(v\) as \(\textit{cntr}\).

Let \(k_1\) be the largest integer such that \(v[\textit{cntr} - k_1 + 1 \dots \textit{cntr}] = u[|u| - k_1 \dots |u| - 1]\), and let \(k_2\) be the largest integer such that \(v[\textit{cntr} + 1 \dots \textit{cntr} + k_2] = v[0 \dots k_2 - 1]\). Then we can obtain \(k_1\) and \(k_2\) by computing the Z-function of \(\overline{u} + \# + \overline{v}\) and \(v\), respectively.

Enumerate \(\textit{cntr}\) and use a similar method to find right-biased tandem repetitions.

Implementation

The Main–Lorentz algorithm outputs all tandem repetitions as quadruples \((\textit{cntr}, l, k_1, k_2)\). If you only need to count the number of tandem repetitions or find the longest tandem repetition, this quadruple provides sufficient information. By the Master Theorem, the time complexity of the Main–Lorentz algorithm is \(O(n \log n)\).

Note that if you want to find the starting and ending positions of all tandem repetitions from these quadruples, the worst-case time complexity becomes \(O(n^2)\). The program below implements this, storing the starting and ending positions of all tandem repetitions in 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);
  }
}

This page is mainly translated from the blog post Поиск всех тандемных повторов в строке. Алгоритм Мейна-Лоренца and its English translation Finding repetitions. The Russian version is licensed under Public Domain + Leave a Link; the English version is licensed under CC-BY-SA 4.0.

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