Simple Linear and Effectively Duval Algorithm for Lyndon Factorization

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	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 cant be factorized. It means that the only factor in its factorization is itself.

3) Lyndon Factorization

Definition: Split the string into many lyndon words in such a way that the words in the sequence are in lexicographically non-increasing order.
Property I: For $$$s = s_1 + s_2 + \dots + s_k$$$ where $$$s_1, s_2, \dots, s_k$$$ are lyndon words and in non-increasing 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 repeated string of Lyndon words
            if (s[r] < s[p]) 
            {
                r = l;
                ++p;
                continue;
            }
        }

        /// The lyndon word may have the form of s2 = sx + sx + .. + sx + sy like "1231231231"
        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
Some other approachs can be found here

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 + sy) 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

Comments (5)

Write comment?

SPyofgame

4 years ago, # |

← Rev. 3 →

In the Dual Elimination Solution, if it has a name, please tag me in

There is a funny thing that the solution still work fine with odd length candidate list

And I think there is an improvement to make it completely Linear

EDIT: I gonna make another blog for that

→ Reply

← Rev. 2 →

Auto comment: topic has been updated by SPyofgame (previous revision, new revision, compare).

Added a little bit more main properties and definitions that might help you understand the algorithm

Lain

You can use Lyndon words to construct a De Bruijn Sequence. See https://github.com/bqi343/USACO/blob/master/Implementations/content/combinatorial%20(11.2)/DeBruijnSeq.h implementation from Benq, which cites this problem.

P.S. sorry for full URL, it seems CF does not like it being embedded.

4 years ago, # ^ |

Thank you, I will add the De Bruijn Sequence Construction soon

query_

12 months ago, # |

It is failing on this testcase

input : abaabbaa

correct output :aaabaabb

user output :aabaabba

code

int duval(const string &s) {

int n = s.size();

int res=0;
for (int l = 0; l < n; )
{
    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 repeated string of Lyndon words
        if (s[r] < s[p]) 
        {
            r = l;
            ++p;
            continue;
        }
    }

    /// The lyndon word may have the form of s2 = sx + sx + .. + sx + sy like "1231231231"
    while (l <= r) 
    {

        res=l;
        l += p - r;
        /// s[l..l + p - r] is sx
    }
}
return res;

}

int main(){

ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

int t=1;
// cin >> t;
while(t--){
    string s;cin >> s;
    int tmp=duval(s);
    rotate(s.begin(),s.begin()+tmp,s.end());
    cout<<s<<"\n";
}

return 0;