string.md

String algorithms

Table of contents

• Lexicographically minimal string rotation
  • Duval’s based algorithm
• Lyndon factorization
  • Duval’s algorithm
• String matching
  • Exact string matching
    • 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.

🔗

• 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 matching

📖

• Ch. 32. String matching – T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein. Introduction to algorithms (2009)
• Ch. 19: String searching – R.Sedgewick. Algorithms (1983)
• Ch. 13: String matching – Drozdek A. Data structures and algorithms in C++ – Cengage Learning (2012)

Exact string matching

📖

• Sec. 13.1: Exact string matching – Drozdek A. Data structures and algorithms in C++ – Cengage Learning (2012)

Knuth–Morris–Pratt algorithm

🔗

• Knuth–Morris–Pratt algorithm – Wikipedia

🎥

• W.Brinkman. KMP searching algorithm (2017)

📖

• Ch. 32. String matching – T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein. Introduction to algorithms (2009)
• Ch. 19: String searching, Sec.: Knuth–Morris–Pratt algorithm – R.Sedgewick. Algorithms (1983)
• Sec. 6.4.2: Knuth–Morris–Pratt’s (KMP) algorithm – S.Halim, F.Halim. Competitive programming (2013)
• Sec. 13.1.2: The Knuth–Morris–Pratt algorithm – Drozdek A. Data structures and algorithms in C++ – Cengage Learning (2012)