String Algorithm: Lyndon Factorization and Duval Algorithm

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	nor	152

Table of content

Teleporter	Description
I. Lyndon Factorization	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

Definition: Lyndon word is a nonempty string that is strictly smaller in lexicographic order than all of its rotations.
Alternatively: Lyndon word is nonempty and lexicographically strictly smaller than any of its proper suffixes.
Alternatively: Let $$$S, T, Z$$$ is nonempty word. $$$S$$$ is Lyndon word if $$$S < T\ \ \ \forall\ S = Z + T$$$
Lyndon factorization is that 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$$$
Special Property: Lyndon factorization is unique.

Notice that the operator + is string concatenation

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 add the codes of these ways later)
Bruteforces Solution: Add all possible acyclic strings into map, the result is the smallest index of the minimal lexicographical string

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

#include <algorithm>
#include <iostream>
#include <map>

using namespace std;
    
int min_cyc(string s)
{
    map<string, int> M;
    for (int i = 0; i < s.size(); ++i)
    {
        if (!M.count(s)) M[s] = i;
        rotate(s.begin(), s.begin() + 1, s.end());
    }
    return (M.begin() -> second);
}

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

Dual Elimination: So I found this "kinda-bruteforces-solution" but suprisingly its complexity is almost Linear. I dont know whether if it has a name, so I named it Dual Elimination

Detail Dual-Elimination Solution - O(n) to O(n log n) Time - O(n) Auxiliary Space

#include <iostream>
#include <vector>

using namespace std;

/// Finding minal string right-rotation to make string minimal lexicographical
int min_cyc(string s)
{
    int n = s.size(); /// For convention: n = |s|

    /// Candidate list
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        a[i] = i; /// Acyclic string start from (i) might the one with minimal lexicographical

    /// For convention
    s += s;

    /// Keep doing dual-elimination until we have the final champion
    while (a.size() > 1)
    {
        /// Next Candidate List
        vector<int> b;
        for (int i = 0; i + 1 < a.size(); i += 2)
        {
            /// Notice that for convention, l < r
            int l = a[i];
            int r = a[i + 1];

            int cmp = 0;
            /// Compare two acyclic strings, whose starting points are (l) and (r) with size (r - l)
            for (int p = r - l - 1; p >= 0; --p, ++l, ++r)
            {
                if (s[l] < s[r]) { cmp = -1; break; }
                if (s[l] > s[r]) { cmp = +1; break; }
            }

            ///
            /// # Case (cmp = -1): Left string is smaller 
            ///   > We will pick (a[i]) as a winner
            ///
            /// # Case (cmp = +1): Right string is smaller
            ///   > We will pick (a[i + 1]) as a winner
            /// 
            /// # Case (cmp == 0): Both string are equal
            ///   > We will pick one whose starting point is smaller
            ///

            b.push_back((cmp <= 0) ? a[i] : a[i + 1]);
        }

        /// The remain candidate that not join the elimination
        if (a.size() & 1) b.push_back(a.back());
        
        /// Do the next elimination
        swap(a, b);
    }

    /// The final winner
    return a.front();
}

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

    /// Output
    cout << min_cyc(s);
    return 0;
}

None-comment Dual-Elimination Solution - O(n) to O(n log n) Time - O(n) Auxiliary Space

#include <iostream>
#include <vector>

using namespace std;

int min_cyc(string s)
{
    int n = s.size();
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        a[i] = i;

    s += s;
    while (a.size() > 1)
    {
        vector<int> b;
        for (int i = 0; i + 1 < a.size(); i += 2)
        {
            int l = a[i];
            int r = a[i + 1];
            int cmp = 0;
            for (int p = r - l - 1; p >= 0; --p, ++l, ++r)
            {
                if (s[l] < s[r]) { cmp = -1; break; }
                if (s[l] > s[r]) { cmp = +1; break; }
            }
            b.push_back((cmp <= 0) ? a[i] : a[i + 1]);
        }
        if (a.size() & 1) b.push_back(a.back());
        swap(a, b);
    }

    return a.front();
}

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

    /// Output
    cout << min_cyc(s);
    return 0;
}

Optimized and Readable Dual-Elimination Solution - O(n) to O(n log n) Time - O(n) Auxiliary Space

#include <iostream>
#include <deque>

using namespace std;

int min_cyc(const string &s)
{
    int n = s.size();
    deque<int> S; 
    for (int i = 0; i < n; ++i)
        S.push_back(i); 

    while (S.size() > 1)
    {
        int a = S.front(); S.pop_front();
        int b = S.front(); S.pop_front();
        if (a > b) swap(a, b);
        int res = min(a, b);
        for (int l = a, r = b, p = r - l - 1; p >= 0; --p, ++l, ++r)
        {
            if (l == n) l = 0;
            if (r == n) r = 0;
            if (s[l] < s[r]) { res = a; break; }
            if (s[l] > s[r]) { res = b; break; }
        }
        S.push_back(res);
    }

    return S.back();
}

int main()
{
    string s;
    cin >> s;
    cout << min_cyc(s);
    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.	Кто	Когда	Δ	Комментарий
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)