Main–Lorentz algorithm

Tandem repetitions

Definition

Given a string $s$ of length $n$.

The new string produced by writing a string twice consecutively is called a tandem repetition. Below, for precision, we call the string being repeated the original string. In other words, a tandem repetition is equivalent 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 a given string $s$. Alternatively, solve the simpler problem of finding any tandem repetition or the longest tandem repetition in $s$.

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

Conventions

All string indices below start from $0$.

Below, let $\overline{s}$ denote the reverse of $s$. For example, $\overline{\tt abc} = \tt cba$.

Explanation

Consider the string $\tt acababaee$. It contains three tandem repetitions:

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

As another example, consider the string $\tt abaaba$. It contains 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$ may have as many as $O(n^2)$ tandem repetitions. An obvious example is a string consisting of $n$ identical letters: in this case, any substring of even length is a tandem repetition. In most cases, a periodic string with a relatively short period has many tandem repetitions.

However, this does not prevent us from calculating the number of tandem repetitions in $O(n \log n)$ time. This is because the algorithm expresses a tandem repetition 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 this tandem repetition a primitive repetition. It can be proved 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 one period of the tandem repetition (note that it is 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.
• Fibonacci strings are defined as follows:

$$\begin{align} t_0 &= a, \\ t_1 &= b, \\ t_i &= t_{i-1} + t_{i-2}, \end{align}$$

It can be seen that Fibonacci strings are highly periodic. For a 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 its 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 divides the string into left and right parts. It first calculates the number of tandem repetitions completely within the left (or right) part, and then calculates the number of tandem repetitions whose starting position is in the left part and whose ending position is in the right part. (Below, we call such tandem repetitions crossing repetitions.)

Calculating the number of crossing repetitions is the key point of the Main–Lorentz algorithm, and we will examine it in detail below.

Process

Finding crossing repetitions

Let the left and right parts of a string be $u, 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 call the first character in the right half of a tandem repetition its middle character; 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 is in $u$, we call it left; otherwise, we call it right.

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

Let the length of a left repetition be $2l$. Consider the first character of this repetition that falls in $v$ (namely $s[|u|]$). This character must match some character $u[\textit{cntr}]$ in $u$.

We fix $\textit{cntr}$ and find all repetitions satisfying the conditions. For example, for the string $\tt c \; \underset{\textit{cntr}}{a} \; c \; | \; a \; d \; a$ (where $\tt |$ is used to distinguish the left and right parts), fixing $cntr = 1$, we can see that the tandem repetition $\tt caca$ satisfies the requirements.

Clearly, once $\textit{cntr}$ is fixed, the value of $l$ is fixed as well. Once we know how to find all repetitions, we can enumerate $\textit{cntr}$ from $0$ to $|u| - 1$ and find all repetitions satisfying the conditions.

Determining left repetitions

Even after fixing $\textit{cntr}$, there may still be multiple tandem repetitions satisfying the conditions. How do we find all of them?

Consider another example. In the string $\tt abcabcac$, take 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}$. Let $l_1$ be the length of the substring from the first character of this 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 original string on the left side of the tandem repetition.

Thus, we can give a 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 every 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.

In summary:

• Fix a $\textit{cntr}$.
• Then all tandem repetitions we seek have length $2l = 2(|u| - \textit{cntr})$. There may still be multiple repetitions satisfying the conditions, depending on the values of $l_1$ and $l_2$.
• Calculate the $k_1$ and $k_2$ mentioned above.
• Then all tandem repetitions satisfying the conditions 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 calculate $k_1$ and $k_2$ quickly. With the help of the Z-function, we can calculate them in $O(1)$:

• To calculate $k_1$: calculate the Z-function of $\overline{u}$.
• To calculate $k_2$: calculate the Z-function of $v + \# + u$, where $\#$ is a character that appears in neither $u$ nor $v$.

Right repetitions

The method for calculating right repetitions is almost identical to that for calculating left repetitions. Consider the first character of this repetition that falls in $u$ (namely $s[|u| - 1]$). It must match some character in $v$; let the position of this character in $v$ be $\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 $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 calculating the Z-functions of $\overline{u} + \# + \overline{v}$ and $v$, respectively.

Enumerate $\textit{cntr}$ and find right repetitions in a similar manner.

Implementation

The Main–Lorentz algorithm gives all tandem repetitions in the form of quadruples $(\textit{cntr}, l, k_1, k_2)$. If you only need to calculate the number of tandem repetitions or find the longest one, the information in this quadruple is sufficient. By the master theorem, the time complexity of the Main–Lorentz algorithm is $O(n \log n)$.

Note that if you want to use these quadruples to find the starting and ending positions of all tandem repetitions, the worst-case time complexity reaches $O(n^2)$. We implement this below, storing the starting and ending positions of all tandem repetitions in repetitions.

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 adapted from the blog Поиск всех тандемных повторов в строке. Алгоритм Мейна-Лоренца 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.