Skip to content

Lyndon Factorization

Definition

We begin with the notion of the Lyndon factorization.

Lyndon word: a nonempty string \(s\) is called a simple string, or a Lyndon word, if it is strictly smaller in lexicographical order than every nonempty proper suffix of \(s\). For example, a, b, ab, aab, abb, ababb and abcd are all Lyndon words. A string \(s\) is a Lyndon word if and only if it is strictly smaller in lexicographical order than all of its nontrivial cyclic shifts (nontrivial: nonempty and different from the string itself).

Lyndon factorization: the Lyndon factorization of a string \(s\) is written \(s=w_1w_2\cdots w_k\), where every \(w_i\) is a simple string and the factors are in non-increasing lexicographical order, that is, \(w_1\ge w_2\ge\cdots\ge w_k\). Such a factorization always exists and is unique.

Duval's algorithm

Explanation

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

First we need one more notion. A string \(t\) that can be written as \(t=ww\cdots\overline{w}\), where \(w\) is a Lyndon word and \(\overline{w}\) is a prefix of \(w\) (possibly the empty string), is called a pre-simple string, or a pre-Lyndon word. A Lyndon word is also a pre-Lyndon word.

Duval's algorithm is greedy. While it runs, the string \(s\) is split into three parts \(s=s_1s_2s_3\): the Lyndon factorization of \(s_1\) has already been recorded, \(s_2\) is a pre-Lyndon word, and \(s_3\) is the part not yet processed.

Procedure

In outline, each step tries to append the first character of \(s_3\) to the end of \(s_2\). If \(s_2\) is then no longer a pre-Lyndon word, we cut a prefix off \(s_2\) (a piece of the Lyndon factorization) and attach it to the end of \(s_1\).

Now in more detail. Let a pointer \(i\) point to the first character of \(s_2\); it runs from \(1\) to \(n\) (the length of the string). Inside the loop, a second pointer \(j\) points to the first character of \(s_3\), and a pointer \(k\) points to the character of \(s_2\) under consideration (the character that corresponds to \(j\) in the previous period of \(s_2\)). We want 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\) keeps it pre-simple. Just increment the pointers \(j\) and \(k\) (move each to the next position).
  2. If \(s[j]>s[k]\), then \(s_2s[j]\) becomes a Lyndon word. Increment \(j\) and point \(k\) at the first character of \(s_2\): now \(s_2\) is a new Lyndon word that consists of a single period.
  3. If \(s[j]<s[k]\), then \(s_2s[j]\) is not a pre-simple string, so we split one Lyndon substring off \(s_2\). Its length is \(j-k\), one period of \(s_2\). Then \(s_2\) becomes what is left after the split, and we repeat (note that the pointers \(j\) and \(k\) do not change in this case) until every period has been cut off. For the part that remains, simply roll back to its first character and continue from there.

Implementation

The code below returns the Lyndon factorization of a string \(s\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
// 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;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
# 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

We now prove the complexity of the algorithm.

The outer loop runs at most \(n\) times, because \(i\) increases in every iteration. The second inner loop is also \(O(n)\), because it only records the Lyndon factorization. It remains to analyze the inner loop. The Lyndon word found in an iteration of the outer loop is longer than the leftover string we compared after it, so the leftover strings have total length less than \(n\) and the inner loop runs at most \(O(n)\) times. In fact the loops run at most \(4n-3\) times in total, and the time complexity is \(O(n)\).

Minimal string rotation

For a string \(s\) of length \(n\), the algorithm above also finds the minimal string rotation.

Build the Lyndon factorization of the string \(ss\) and look in it for a Lyndon word \(t\) that starts at a position less than \(n\) and ends at a position greater than or equal to \(n\). The properties of the Lyndon factorization make it easy to prove that the first character of the substring \(t\) is the first character of the minimal string rotation of \(s\): the \(n\) characters from the start of \(t\) onward form the minimal string rotation of \(s\).

So it is enough to record, during the factorization, where each pre-Lyndon word begins.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
// 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);
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
# 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]

Practice problems