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
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
- Better Solution: Let $$$t = s + s$$$. Then for each substring of size $$$|s|$$$, we compare and find the smallest
- Duval Solution: We can apply lyndon factorization with a little bit observation
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