Lyndon factorization

Definition

We first introduce the concept of Lyndon factorization.

For a string $s$, if the lexicographic order of $s$ is strictly smaller than that of every suffix of $s$, we call $s$ a simple string, or a Lyndon string. For example, a, b, ab, aab, abb, ababb, and abcd are all Lyndon strings. Equivalently, $s$ is a Lyndon string if and only if its lexicographic order is strictly smaller than that of every nontrivial conjugate string of $s$ (nontrivial means nonempty and different from itself).

The Lyndon factorization of a string $s$ is written as $s=w_1w_2\cdots w_k$, where every $w_i$ is a Lyndon string and their lexicographic orders are sorted in non-increasing order, that is, $w_1\ge w_2\ge\cdots\ge w_k$. This factorization exists and is unique.

Duval algorithm

Explanation

Duval's algorithm finds the Lyndon factorization of a string in $O(n)$ time.

First, we introduce another concept. If a string $t$ can be decomposed in the form $t=ww\cdots\overline{w}$, where $w$ is a Lyndon string and $\overline{w}$ is a prefix of $w$ ($\overline{w}$ may be the empty string), then $t$ is called a pre-simple string, or a pre-Lyndon string. Every Lyndon string is also a pre-Lyndon string.

Duval's algorithm is greedy. During the algorithm, we split $s$ into three parts, $s=s_1s_2s_3$, where $s_1$ is a Lyndon string whose Lyndon factorization has already been recorded; $s_2$ is a pre-Lyndon string; and $s_3$ is the unprocessed part.

Procedure

In broad terms, at each step the algorithm tries to append the first character of $s_3$ to the end of $s_2$. If $s_2$ is no longer a pre-Lyndon string, we can cut off a prefix of $s_2$ (that is, a Lyndon factor) and append it to the end of $s_1$.

Let pointer $i$ point to the first character of $s_2$, so that $i$ ranges from $1$ to $n$, the length of the string. During the loop, let pointer $j$ point to the first character of $s_3$, and pointer $k$ point to the character currently being considered in $s_2$ (that is, the character corresponding to $j$ in the preceding period of $s_2$). Our goal is to append $s[j]$ to the end of $s_2$, so we compare $s[j]$ with $s[k]$:

1. If $s[j]=s[k]$, appending $s[j]$ to the end of $s_2$ does not affect its pre-simple property. We only need to increment pointers $j,k$, moving them to the next positions.
2. If $s[j]>s[k]$, then $s_2s[j]$ becomes a Lyndon string. We increment $j$ and let $k$ point to the first character of $s_2$, so that $s_2$ becomes a new Lyndon string with one repetition.
3. If $s[j]<s[k]$, then $s_2s[j]$ is no longer pre-simple. We must split a Lyndon substring from $s_2$; its length is $j-k$, namely the length of one period. We then replace $s_2$ with the part remaining after the split and continue the loop (note that in this case we do not change pointers $j,k$), until the period has been completely removed. For the remaining part, we only need to roll the progress back to the beginning of that part.

Implementation

The following code returns the Lyndon factorization of the string $s$.

C++

// duval_algorithm
vector<string> duval(string const& s) {
  int n = s.size(), i = 0;
  vector<string> factorization;
  while (i < n) {
    int j = i + 1, k = i;
    while (j < n && s[k] <= s[j]) {
      if (s[k] < s[j])
        k = i;
      else
        k++;
      j++;
    }
    while (i <= k) {
      factorization.push_back(s.substr(i, j - k));
      i += j - k;
    }
  }
  return factorization;
}

Python

# duval_algorithm
def duval(s):
    n, i = len(s), 0
    factorization = []
    while i < n:
        j, k = i + 1, i
        while j < n and s[k] <= s[j]:
            if s[k] < s[j]:
                k = i
            else:
                k += 1
            j += 1
        while i <= k:
            factorization.append(s[i : i + j - k])
            i += j - k
    return factorization

Complexity analysis

Next, we prove the complexity of this algorithm.

The outer loop runs at most $n$ times, because $i$ increases on every iteration. The second inner loop is also $O(n)$, since it only records the Lyndon factorization. We now analyze the inner loop. It is easy to see that every Lyndon string found in an iteration of the outer loop is longer than the remaining string that we have compared. Therefore, the sum of the lengths of the remaining strings is less than $n$, and the inner loop runs at most $O(n)$ times. In fact, the total number of iterations is at most $4n-3$, so the time complexity is $O(n)$.

Minimal representation (Finding the smallest cyclic shift)

For a string of length $n$, denoted by $s$, we can use the algorithm above to find its minimal representation.

We construct the Lyndon factorization of $ss$, then find a Lyndon string $t$ in this factorization whose starting position is less than $n$ and whose ending position is at least $n$. It is easy to prove from the properties of Lyndon factorization that the first character of $t$ is the first character of the minimal representation of $s$; in other words, starting from the beginning of $t$, the string of the next $n$ characters is the minimal representation of $s$.

Thus, during the factorization, we only need to record the beginning of each pre-Lyndon string.

C++

// smallest_cyclic_string
string min_cyclic_string(string s) {
  s += s;
  int n = s.size();
  int i = 0, ans = 0;
  while (i < n / 2) {
    ans = i;
    int j = i + 1, k = i;
    while (j < n && s[k] <= s[j]) {
      if (s[k] < s[j])
        k = i;
      else
        k++;
      j++;
    }
    while (i <= k) i += j - k;
  }
  return s.substr(ans, n / 2);
}

Python

# smallest_cyclic_string
def min_cyclic_string(s):
    s += s
    n = len(s)
    i, ans = 0, 0
    while i < n / 2:
        ans = i
        j, k = i + 1, i
        while j < n and s[k] <= s[j]:
            if s[k] < s[j]:
                k = i
            else:
                k += 1
            j += 1
        while i <= k:
            i += j - k
    return s[ans : ans + n / 2]

Exercises

• UVa #719 - Glass Beads

  This page is mainly translated from the blog post Lyndon Decomposition. Duval's Algorithm. Finding the Smallest Cyclic Shift and its English translation Lyndon factorization. The Russian version is licensed under Public Domain + Leave a Link; the English version is licensed under CC-BY-SA 4.0.