Skip to content

Lyndon Decomposition

Definition

First, we introduce the concept of Lyndon decomposition.

Lyndon word: For a string \(s\), if the lexicographic order of \(s\) is strictly smaller than the lexicographic order of all suffixes of \(s\), we call \(s\) a simple string, or a Lyndon word. Some examples: a, b, ab, aab, abb, ababb, abcd are all Lyndon words. A string \(s\) is a Lyndon word if and only if its lexicographic order is strictly smaller than all its non-trivial (non-trivial: non-empty and not equal to itself) cyclic shifts.

Lyndon decomposition: The Lyndon decomposition of a string \(s\) is denoted as \(s=w_1w_2\cdots w_k\), where all \(w_i\) are simple strings (Lyndon words), and their lexicographic order is non-strictly decreasing, i.e., \(w_1\ge w_2\ge\cdots\ge w_k\). It can be shown that such a decomposition exists and is unique.

Duval's Algorithm

Explanation

Duval's algorithm can compute the Lyndon decomposition of a string in \(O(n)\) time.

First, we introduce another concept: If a string \(t\) can be decomposed as \(t=ww\cdots\overline{w}\), where \(w\) is a Lyndon word and \(\overline{w}\) is a prefix of \(w\) (which may be empty), then \(t\) is called a pre-simple string, or an approximate Lyndon word. A Lyndon word is also an approximate Lyndon word.

Duval's algorithm uses a greedy approach. During the algorithm, we partition the string \(s\) into three parts \(s=s_1s_2s_3\), where \(s_1\) is a Lyndon word whose Lyndon decomposition has already been recorded; \(s_2\) is an approximate Lyndon word; and \(s_3\) is the unprocessed part.

Process

In general, the algorithm attempts to append the first character of \(s_3\) to the end of \(s_2\) each time. If \(s_2\) is no longer an approximate Lyndon word, then we can extract a prefix (i.e., a Lyndon decomposition) from \(s_2\) and append it to \(s_1\).

Let's explain the algorithm process in more detail. Define a pointer \(i\) pointing to the first character of \(s_2\), so \(i\) iterates from \(1\) to \(n\) (the length of the string). During the loop, we define another pointer \(j\) pointing to the first character of \(s_3\), and a pointer \(k\) pointing to the character in \(s_2\) we are currently considering (meaning \(j\) corresponds to the character in the previous cycle of \(s_2\)). Our goal is to add \(s[j]\) to the end of \(s_2\), which requires comparing \(s[j]\) with \(s[k]\):

  1. If \(s[j]=s[k]\), then adding \(s[j]\) to the end of \(s_2\) does not affect its approximate simplicity. We simply increment pointers \(j\) and \(k\) (move to the next position).
  2. If \(s[j]>s[k]\), then \(s_2s[j]\) becomes a Lyndon word. We increment \(j\) and set \(k\) to point to the first character of \(s_2\), so \(s_2\) becomes a new Lyndon word with a cycle length of 1.
  3. If \(s[j]<s[k]\), then \(s_2s[j]\) is no longer an approximate Lyndon word. We then decompose \(s_2\) into one of its Lyndon substrings, whose length will be \(j-k\), i.e., one of its cycles. Then, we set \(s_2\) to the remaining part after decomposition and continue the loop (note: in this case, we do not change pointers \(j\) and \(k\)) until the cycle is fully extracted. For the remaining part, we simply "roll back" the progress to the beginning of the remaining part.

Implementation

The following code returns the Lyndon decomposition of 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

Next, we prove the complexity of this algorithm.

The outer loop runs at most \(n\) times because \(i\) increases each time. The second inner loop is also \(O(n)\) because it only records the Lyndon decomposition. Now let's analyze the inner loop. It is easy to see that each Lyndon word found in the outer loop is longer than the remaining strings we have compared, so the total length of the remaining strings is less than \(n\). Therefore, the inner loop runs at most \(O(n)\) times. In fact, the total number of iterations does not exceed \(4n-3\), so the time complexity is \(O(n)\).

Finding the smallest cyclic shift

For a string \(s\) of length \(n\), we can use the above algorithm to find its smallest cyclic shift.

We construct the Lyndon decomposition of the string \(ss\), then find a Lyndon word \(t\) in this decomposition such that its starting index is less than \(n\) and its ending index is greater than or equal to \(n\). It can be easily proven using the properties of Lyndon decomposition that the first character of substring \(t\) is the first character of the smallest cyclic shift of \(s\), i.e., the string formed by taking \(n\) characters starting from the beginning of \(t\) is the smallest cyclic shift of \(s\).

Thus, during the decomposition process, we only need to record the starting index of each approximate Lyndon word.

 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]

Exercises

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