Simple Linear and Effectively Duval Algorithm for Lyndon Factorization

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	adamant	157
6	awoo	157
8	TheScrasse	154
8	nor	154
10	djm03178	153

Table of content

Teleporter	Description
I. Lyndon Definitions	Definitions of Lyndon word, Lyndon factorization, ...
II. Duval Algorithm	Talk about the duval algorithm and how it works
III. Real Life Applications	Motivation to learn the algorithm
IV. Programming Applications	The code is short and simple to implement
V. My Questions	Are there any other applications ?
...................................................................	..........................................................................................................................

I. Lyndon Factorization

1) String Concatenation

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

2) Lyndon Word

Definition: A nonempty string that is strictly smaller in lexicographic order than all of its rotations.
Property I: Lyndon word is nonempty and lexicographically strictly smaller than any of its proper suffixes.
Property II: Let $$$S, T, Z$$$ is nonempty word. $$$S$$$ is Lyndon word if $$$S < T\ \ \ \forall\ S = Z + T$$$
Property III: Lyndon word is MLCS — Minimal Lexicographical Circular Substring or ( LMSR — Lexicographically Minimal String Rotation ) of itself.

3) Lyndon Factorization

Definition: Split the string into many lyndon words in such a way that the words in the sequence are nonincreasing lexicographically
Property I: For $$$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$$$
Property II: Lyndon factorization is unique.
Property III: The last Lyndon Factor is Lexicographically Smallest Suffix of the string

4) Least Starting Position (LSP)

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 Rotation

II. Duval Algorithm

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

The pseudo algorithm

Implementation - O(n) Time - O(1) Auxiliary Space

#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;
}

Detail Implementation - O(n) Time - O(1) Auxiliary Space


#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;
}

III. Real Life Applications

1) Finger print identification:

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.

2) Biological genetics:

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

3) Games:

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

IV. Programming Applications

1) Least rotation to make smallest lexicographical ordered string.

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

Bruteforces Solution - O(n^2) Time - O(n) Auxiliary Space

#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;
}

Optimized Bruteforces Solution - O(n) to O(n^2) Time - O(n) Auxiliary Space

#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;
}

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

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

#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;
}

None-comment Duval Solution - O(n) Time - O(n) Auxiliary Space

#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;
}

Optimized Duval Solution - O(n) Time - O(1) Auxiliary Space

#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;
}

Practices Problem:

V. My Question

1) Are there any other programming applications for Lyndon Factorization ?

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 :(

2) Are there any other problems for Lyndon Factorization ?

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

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