string.md

String algorithms

Table of contents

• Lexicographically minimal string rotation
  • Duval’s based algorithm
• Lyndon factorization
  • Duval’s algorithm
• String searching
  • Knuth–Morris–Pratt algorithm

---

Lexicographically minimal string rotation

Lexicographically minimal rotation if the rotation of a string possessing the lowest lexicographical order of all its rotations.

🔗

• Lexicographically minimal string rotation – Wikipedia

Duval’s based algorithm

📝

• This algorithm is also known as the Zhou Yuan’s minimal expression algorithm.

🔗

• Lyndon factorization – CP-Algorithms
• How does the minimum expression algorithm by Zhou Yuan work? – Quora

---

Lyndon factorization

Lyndon word is a (non-empty) string that is strictly smaller in lexicographic order than all of its rotations. Lyndon factorization is a decomposition of a string s into Lyndon words, s = w1w2...wn, such that w1 ≥ wi ≥ ... ≥ wn.

📝

• Lexicographically minimal string rotation
  • Duval’s based algorithm
• Lyndon factorization
  • Duval’s algorithm
• String searching
  • Knuth–Morris–Pratt algorithm

🔗

• Lyndon word – Wikipedia

Duval’s algorithm

🔗

• Lyndon factorization – CP-Algorithms

📄

• J.P.Duval. Factorizing words over an ordered alphabet – Journal of algorithms 8, 363 (1983)
• S.S.Ghuman, E.Giaquinta, J.Tarhio. Alternative algorithms for Lyndon factorization – arXiv preprint (2014)

---

String searching

Knuth–Morris–Pratt algorithm

🔗

• Knuth–Morris–Pratt algorithm – Wikipedia

🎥

• W.Brinkman. KMP searching algorithm (2017)