Simple Linear and Effectively Duval Algorithm for Lyndon Factorization
Difference between en12 and en13, changed 1,961 character(s)
--------------------↵

--------------------↵

--------------------↵

### <strong> <center style="color:red;"> Table of content </center> </strong> ↵

| Teleporter                                   | Description                                       
     |↵
| :------------------------------------------- | :------------------------------------------------
----- |↵
| [I. Lyndon 
FactorizaDefinitions](#lyndon)             | Definitions of Lyndon word, Lyndon factorization, ...  |↵
| [II. Duval Algorithm](#duval)                | Talk about the duval algorithm and how it works   
     |↵
| [III. Real Life Applications](#rla)          | Motivation to learn the algorithm                 
     |↵
| [IV. Programming Applications](#application) | The code is short and simple to implement         
     |↵
| [V. My Questions](#question)                 | Are there any other applications ? 
                    |↵
| ................................................................... |.......................................................................................................................... |↵

 ↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

<a name="lyndon"></a>↵

### <strong> <center style="color:red;"> I. Lyndon Factorization </center> </strong> ↵

--------------------------↵


--------------------------↵

- **Definition:** Lyndon word is a
--------------------------↵

##### <span style="color:green;"> **1)** String Concatenation </span>↵

--------------------------↵

- **Definition:** The operation of joining character strings end-to-end↵

- Property I: Non-empty string $S$ is a concatenation of all substrings of itself↵

- Property II: Non-empty string $S$ is a concatenation of any empty string at any position in itself with itself↵

- Property III: Let $A, B, C$ the non-empty string then $A + B + C = A + (B + C) = (A + B) + C$↵

- For convention, let define the operator **+** is **string concatenation**↵

--------------------------↵

--------------------------↵

##### <span style="color:green;"> **2)** Lyndon Word </span>↵

--------------------------↵


- **Definition:** A
 nonempty string that is strictly smaller in lexicographic order than all of its rotations.↵

**Alternatively:**Property I: Lyndon word is nonempty and lexicographically strictly smaller than any of its proper suffixes.↵

**Alternatively:**Property II: Let $S, T, Z$ is nonempty word. $S$ is Lyndon word if $S < T\ \ \ \forall\ S = Z + T$↵

**Lyndon factorization** is that fProperty III: Lyndon word is **MLCS &mdash; Minimal Lexicographical Circular Substring** or ( **LMSR &mdash; Lexicographically Minimal String Rotation** ) of itself.↵

--------------------------↵

--------------------------↵

##### <span style="color:green;"> **3)** Lyndon Factorization </span>↵

--------------------------↵


- **Definition:** Split the string into many lyndon words in such a way that the words in the sequence are nonincreasing lexicographically↵

- Property I: F
or $s = s_1 + s_2 + \dots + s_k$ where $s_i$ is nonempty shortest-able string and in decreasing order $s1 \geq s2 \geq \dots \geq s_k$↵

**Special Property:** II: Lyndon factorization is **unique**.↵

> Notice that the operator **+** is **string concaten- Property III: The last Lyndon Factor is Lexicographically Smallest Suffix of the string↵


--------------------------↵

--------------------------↵

##### <span style="color:green;"> **4)** Least Starting Position (LSP) </span>↵

--------------------------↵

- **Definition:** The minimal position of some substrings that make it **LMSR**. ↵

- Property I: Let $X$ the substring of $S$ that its starting position $p$ is LSP. Then some Lyndon Factors in $X$ has the LSP $p$↵

- Property II: $K$-repeated String, where each substring has size $L$ then there are $K$ LSP: $0, L, 2L, \dots, (K-1)L$↵

- Property III: The Circular String start from LSP of given string is **Lexicographically Minimal String Rot
ation**↵
 ↵


























--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

<a name="duval"></a>↵

### <strong> <center style="color:red;"> II. Duval Algorithm </center> </strong> ↵

--------------------------↵

--------------------------↵

- **Exist Time:** 1983↵

- **Duval algorithm** is an effecient algorithm for listing the Lyndon words of length at most $n$ with a given alphabet size $s$ in lexicographic order in $O(n)$↵

- The position of the last Lyndon factorized word from Duval algorithm provides minimum cyclic string↵

<spoiler summary="The pseudo algorithm">↵

For string $S$ of length $n$↵

For each new word $x$ from $S$ that $\forall i$ we have $x[i] = s[i mod n]$ (mean $x$ is a sub-string of some cyclic strings that shifted from initial $S$)↵

While the last symbol of $x$ is in sorted order, remove it to make a shorter word↵

Replace the last remained symbol of $x$ by its successor in sorted order.↵

</spoiler>↵

<spoiler summary="Implementation - O(n) Time - O(1) Auxiliary Space">↵

```cpp↵
#include <iostream>↵

using namespace std;↵

void duval(const string &s)↵
{↵
    int n = s.size();↵
    for (int l = 0; l < n; )↵
    {↵
        int r = l, p = l + 1;↵
        for (; r < n && s[r] <= s[p]; ++r, ++p)↵
            if (s[r] < s[p]) r = l - 1;↵

        while (l <= r)↵
        {↵
            cout << s.substr(l, p - r) << '\n';↵
            l += p - r;↵
        }↵
    }↵
}↵

int main()↵
{↵
    string s;↵
    cin >> s;↵
    duval(s);↵
    return 0;↵
}↵
```↵
</spoiler>↵

<spoiler summary="Detail Implementation - O(n) Time - O(1) Auxiliary Space">↵

```cpp↵

#include <iostream>↵

using namespace std;↵

/// Factorize all lyndon word in s↵
void duval(const string &s)↵
{↵
    int n = s.size();↵

    ///↵
    /// s = s1 + s2 + s3↵
    /// s1 = s[1..l-1] is handled↵
    /// s2 = s[l..r]   is handling↵
    /// s3 = s[p..n]   is going to be handled↵
    /// ↵

    for (int l = 0; l < n; )↵
    {↵
        /// Extend as much as possible lyndon word s2 = s[l..r]↵
        int r = l, p = l + 1;↵
        while (r < n)↵
        {↵
            /// (s2 + s[p]) is not a lyndon word↵
            if (s[r] > s[p]) ↵
            {↵
                break;↵
            }↵

            /// (s2 + s[p]) is stil a lyndon word, hence extend s2↵
            if (s[r] == s[p]) ↵
            {↵
                ++r;↵
                ++p;↵
                continue;↵
            }↵
            ↵
            /// (s2 + s[p]) is a lyndon word, but it may be a repeated string↵
            if (s[r] < s[p]) ↵
            {↵
                r = l;↵
                ++p;↵
                continue;↵
            }↵
        }↵

        /// The lyndon word may have the form of s2 = sx + sx + .. + sx like "12312123"↵
        while (l <= r) ↵
        {↵
            /// s[l..l + p - r] is sx↵
            cout << s.substr(l, p - r) << '\n';↵
            l += p - r;↵
        }↵
    }↵
}↵

int main()↵
{↵
    string s;↵
    cin >> s;↵
    duval(s);↵
    return 0;↵
}↵
```↵
</spoiler>↵






























--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵


<a name="rla"></a>↵

### <strong> <center style="color:red;"> III. Real Life Applications </center> </strong> ↵

--------------------------↵

--------------------------↵

##### <span style="color:green;"> **1)** Finger print identification: </span>↵


- We can encode the finger print into many detailed circular strings. How to search such finger print again from those in very huge data base ? Circular comparision using lyndon factorization is requried.↵

--------------------------↵

##### <span style="color:green;"> **2)** Biological genetics:  </span>↵

- In some cases, we need to know whether these two group's genetics are belonged to the same bacteria, virus.↵

--------------------------↵

##### <span style="color:green;"> **3)** Games:  </span>↵

- Well, ofcourse we can apply the algorithm in some language/words-related games↵













--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

<a name="application"></a>↵

### <strong> <center style="color:red;"> IV. Programming Applications </center> </strong> ↵

--------------------------↵

--------------------------↵


##### <span style="color:green;"> **1)** Least rotation to make smallest lexicographical ordered string. </span>↵

--------------------------↵

--------------------------↵

###### **The problem:**↵

- Given a string $S$ of size $N$↵

- A right-rotation is that move the leftmost character to rightmost of $S$↵

- Find the least right-rotation to make $S$ become the smallest lexicographical ordered string↵

**Important Property:** After those right-rotations, the string will be Minimum Acyclic String↵

--------------------------↵

--------------------------↵

###### **The solution:**↵

- One thing we can come in mind is to use hash or string algorithms in $O(n\ log\ n)$, but they are kinda complex↵

- I will make a new blog about all other approachs↵

--------------------------↵

- **Bruteforces Solution:** Let $t = s + s$. Then for each substring of size $|s|$, we compare and find the smallest↵

<spoiler summary="Bruteforces Solution - O(n^2) Time - O(n) Auxiliary Space">↵

```cpp↵
#include <iostream>↵

using namespace std;↵

int main()↵
{↵
    string s;↵
    cin >> s;↵
    int n = s.size();↵
    s += s;↵

    int t = 0;↵
    for (int i = 1; i < n; ++i)↵
        if (s.substr(i, n) < s.substr(t, n))↵
            t = i;↵

    cout << t;↵
    return 0;↵
}↵
```↵
</spoiler>↵


<spoiler summary="Optimized Bruteforces Solution - O(n) to O(n^2) Time - O(n) Auxiliary Space">↵

```cpp↵
#include <iostream>↵

using namespace std;↵

int main()↵
{↵
    string s;↵
    cin >> s;↵
    int n = s.size();↵
    s += s;↵

    int t = 0;↵
    for (int i = 1; i < n; ++i)↵
    {↵
        int cmp = 0; /// EQUAL↵
        for (int p = n, l = t, r = i; p > 0; --p, ++l, ++r)↵
        {↵
            if (s[l] < s[r]) { cmp = -1; break; } ///  LESS ↵
            if (s[l] > s[r]) { cmp = +1; break; } /// GREATER↵
        }↵

        if (cmp == +1) t = i;↵
    }↵

    cout << t;↵
    return 0;↵
}↵
```↵
</spoiler>↵

--------------------------↵

- **Duval Solution:** We can apply lyndon factorization with a little bit observation↵

<spoiler summary="Detail Duval Solution - O(n) Time - O(n) Auxiliary Space">↵

- The idea is that when we factorize duplicated string $t = s + s$↵

- Then the answer will be a substring of maximum starting position $p$ not exceed $|s|$↵

- The proves is already inside the code↵

```cpp↵
#include <algorithm>↵
#include <iostream>↵

using namespace std;↵

/// Find starting position of minimum acyclic string in (s)↵
int min_cyc(string s)↵
{↵
    int n = s.size(); /// the real size of the string↵
    s += s; /// for convention since we are deadling with acyclic↵

    ///↵
    /// s = s1 + s2 + s3↵
    /// s1 = s[1..l-1] is handled↵
    /// s2 = s[l..r]   is handling↵
    /// s3 = s[p..n]   is going to be handled↵
    /// ↵

    int res = 0; /// minimum acyclic string↵
    /// while (s2) is a lyndon word, try to add s2 with s[p]↵
    for (int l = 0; l < n; )↵
    {↵
        ///↵
        /// - Case 1: ↵
        ///     If (s) is fully ordered, then return 0↵
        ///     Surely will this loop make [l..r] = [0..n-1]↵
        ///     Ans it is currently that (l = 0) ↵
        ///     => res = l is a correct answer↵
        ///↵
        /// - Case 2:↵
        ///     Minimum acyclic string s' = s[l..r] that 0 <= l < n <= r < 2n↵
        ///     Also if s2 is s', then the loop will extend its (r >= n)↵
        ///     Since l < n, the latest (l) will create s'    ↵
        ///     => res = l is a correct answer↵
        /// ↵
        /// Hence in both cases, res = last(l) will return a correct answer↵
        ///↵
        res = l;↵

        /// Extend as much as possible lyndon word s2 = s[l..r]↵
        int r = l, p = l + 1;↵
        while (p < s.size())↵
        {↵
            /// (s2 + s[p]) is not a lyndon word↵
            if (s[r] > s[p]) ↵
            {↵
                break;↵
            }↵

            /// (s2 + s[p]) is stil a lyndon word, hence extend s2↵
            if (s[r] == s[p]) ↵
            {↵
                ++r;↵
                ++p;↵
                continue;↵
            }↵
            ↵
            /// (s2 + s[p]) is a lyndon word, but it may be a repeated string↵
            if (s[r] < s[p]) ↵
            {↵
                r = l;↵
                ++p;↵
                continue;↵
            }↵
        }↵

        /// The lyndon word may have the form of s2 = sx + sx + .. + sx like "12312123"↵
        while (l <= r) ↵
        {↵
            /// s[l..l + p - r] is sx↵
            l += p - r;↵
        }↵
    }↵

    /// Dont forget to return the value ;)↵
    return res;↵
}↵

/// If you wanna know about that minimum acyclic string↵
string cyc(string s, int k)↵
{↵
    rotate(s.begin(), s.begin() + k, s.end());↵
    return s;↵
}↵

int main()↵
{↵
    /// Input ↵
    string s;↵
    cin >> s;↵

    /// Output↵
    cout << min_cyc(s) << '\n';↵
//  cout << cyc(s, min_cyc(s));↵
    return 0;↵
}↵
```↵
</spoiler>↵


<spoiler summary="None-comment Duval Solution - O(n) Time - O(n) Auxiliary Space">↵

```cpp↵
#include <iostream>↵

using namespace std;↵

int min_cyc(string s)↵
{↵
    int n = s.size();↵
    s += s;↵

    int res = 0;↵
    for (int l = 0; l < n; )↵
    {↵
        res = l;↵
        int r = l, p = l + 1;↵
        for (; p < s.size() && s[r] <= s[p]; ++r, ++p)↵
            if (s[r] < s[p]) r = l - 1;↵

        while (l <= r) l += p - r;↵
    }↵

    return res;↵
}↵

int main()↵
{↵
    string s;↵
    cin >> s;↵
    cout << min_cyc(s) << '\n';↵
    return 0;↵
}↵
``` ↵
</spoiler>↵

<spoiler summary="Optimized Duval Solution - O(n) Time - O(1) Auxiliary Space">↵

```cpp↵
#include <iostream>↵
    ↵
using namespace std;↵
    ↵
int min_cyc(const string &s) ↵
{↵
    int n = s.size();↵
    int res = 0;↵
    for (int l = 0; l < n; )↵
    {↵
        res = l;↵
        int r = l, p = l + 1;↵
        for (; r < n; ++r, ++p) /// If there is such string found, then its length wont exceed |s|↵
        {↵
            char c = (p < n) ? s[p] : s[p - n]; /// to avoid modulo↵
            if (s[r] > c) break;↵
            if (s[r] < c) r = l - 1;↵
        }        ↵
        l = max(r, l + p - r); /// just skip those (s2 = sx + sx + ... + sx) cases↵
    }↵
    return res;↵
}↵

int main()↵
{↵
    string s;↵
    cin >> s;↵
    cout << min_cyc(s);↵
    return 0;↵
}↵
```↵
</spoiler>↵

--------------------------↵

**Practices Problem:**↵

- [CSES &mdash; Minimal Rotation](https://cses.fi/problemset/task/1110/)↵

- [SPOJ &mdash; Minimum Rotations](https://www.spoj.com/problems/MINMOVE/)↵

- [UVA &mdash; Glass Beads](https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=660)↵


































--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

--------------------------↵

<a name="question"></a>↵

### <strong> <center style="color:red;"> V. My Question </center> </strong> ↵

--------------------------↵

--------------------------↵


##### <span style="color:green;"> **1)** Are there any other programming applications for **Lyndon Factorization** ? </span>↵

- The algorithm is simple to code while running pretty fast as its low complexities. It would be kinda sad if there is only one main application, isnt it :(↵

--------------------------↵

##### <span style="color:green;"> **2)** Are there any other problems for **Lyndon Factorization** ? </span>↵

- To remember something better and understand the algorithm deeper, we need to practice right :D It would be nice if there are some more problems

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en26 English SPyofgame 2021-04-25 17:04:35 91
en25 English SPyofgame 2021-04-23 07:30:37 5 Tiny change: '+ ... + sx) cases\n ' -> '+ ... + sx + sy) cases\n '
en24 English SPyofgame 2021-04-23 05:33:30 0 (published)
en23 English SPyofgame 2021-04-23 05:33:05 128759 Reverted to en21
en22 English SPyofgame 2021-04-23 05:32:05 128759 (saved to drafts)
en21 English SPyofgame 2021-04-23 03:18:18 240
en20 English SPyofgame 2021-04-23 02:58:45 634
en19 English SPyofgame 2021-04-22 19:45:39 2 Tiny change: 'x[i] = s[i mod n]$ (mean' -> 'x[i] = s[i\ mod\ n]$ (mean'
en18 English SPyofgame 2021-04-22 19:27:38 30
en17 English SPyofgame 2021-04-22 19:26:32 17
en16 English SPyofgame 2021-04-22 19:19:53 0 (published)
en15 English SPyofgame 2021-04-22 19:19:36 137 (saved to drafts)
en14 English SPyofgame 2021-04-22 19:13:13 49
en13 English SPyofgame 2021-04-17 12:52:26 1961
en12 English SPyofgame 2021-04-15 02:55:21 60
en11 English SPyofgame 2021-04-14 22:41:27 24 Tiny change: '------\n\n' -> '------\n\n--------------------\n\n'
en10 English SPyofgame 2021-04-14 16:57:32 9 Tiny change: '-\n\n- **Better Solution:' -> '-\n\n- **Bruteforces Solution:'
en9 English SPyofgame 2021-04-14 16:57:02 5097
en8 English SPyofgame 2021-04-14 16:54:37 1196
en7 English SPyofgame 2021-04-14 15:25:50 76
en6 English SPyofgame 2021-04-14 15:19:41 6687 Tiny change: 'oiler>\n\n------' -> 'oiler>\n\n\n\n------'
en5 English SPyofgame 2021-04-14 14:29:22 76
en4 English SPyofgame 2021-04-14 04:57:52 12
en3 English SPyofgame 2021-04-14 04:55:32 1 Tiny change: '.... |\n\n\n\n------' -> '.... |\n\n \n\n------'
en2 English SPyofgame 2021-04-13 16:58:24 439
en1 English SPyofgame 2021-04-13 16:54:43 13595 Initial revision (published)