--------------------↵
↵
--------------------↵
↵
--------------------↵
↵
### <strong> <center style="color:red;"> Table of content </center> </strong> ↵
↵
| Teleporter | Description |↵
| :------------------------------------------- | :----------------------------------------------------- |↵
| [I. LyndonFactorizaDefinitions](#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 — Minimal Lexicographical Circular Substring** or ( **LMSR — 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: 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:** 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 Rotation**↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
--------------------------↵
↵
--------------------------↵
↵
--------------------------↵
↵
--------------------------↵
↵
--------------------------↵
↵
--------------------------↵
↵
--------------------------↵
↵
--------------------------↵
↵
--------------------------↵
↵
--------------------------↵
↵
<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 — Minimal Rotation](https://cses.fi/problemset/task/1110/)↵
↵
- [SPOJ — Minimum Rotations](https://www.spoj.com/problems/MINMOVE/)↵
↵
- [UVA — 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
↵
--------------------↵
↵
--------------------↵
↵
### <strong> <center style="color:red;"> Table of content </center> </strong> ↵
↵
| Teleporter | Description |↵
| :------------------------------------------- | :----------------------------------------------------- |↵
| [I. Lyndon
| [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.↵
↵
-
↵
-
↵
-
↵
--------------------------↵
↵
--------------------------↵
↵
##### <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: 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$↵
↵
-
↵
↵
↵
--------------------------↵
↵
--------------------------↵
↵
##### <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 Rotation**↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
--------------------------↵
↵
--------------------------↵
↵
--------------------------↵
↵
--------------------------↵
↵
--------------------------↵
↵
--------------------------↵
↵
--------------------------↵
↵
--------------------------↵
↵
--------------------------↵
↵
--------------------------↵
↵
<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 — Minimal Rotation](https://cses.fi/problemset/task/1110/)↵
↵
- [SPOJ — Minimum Rotations](https://www.spoj.com/problems/MINMOVE/)↵
↵
- [UVA — 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
