Tag
string-indexing
- Mar 25, 2026 From Suffix Trie to Suffix Array: Implicit Nodes and Intervals A suffix trie over a text is quadratic in nodes; a suffix tree keeps only branching positions; a suffix array replaces the nodes with sorted offsets plus an LCP array. What is gained and lost at each step. data structures
- Oct 4, 2024 Suffix Arrays, Prefix Doubling, and the Kasai LCP Scan How sorting all suffixes of a text supports substring queries with one integer array, why doubling sorts in O(n log n), and how the LCP array is computed in a single pass. algorithms
- Jan 11, 2024 The Burrows–Wheeler Transform and Backward Search in the FM-Index Why sorting cyclic rotations clusters equal characters, how the LF mapping inverts the transform, and how the same mapping turns the last column into a searchable index. algorithms
- Dec 28, 2023 Lyndon Factorization and the Structure of Minimal Rotations How Duval splits any word into a non-increasing sequence of Lyndon words in linear time, why the longest Lyndon prefix equals the next smaller suffix, and how that decides the smallest rotation. algorithms
- Sep 13, 2022 Suffix Automata and Counting Distinct Substrings Online How a suffix automaton stores every substring of a text in linear states, why cloning a state preserves end-position sets, and how the state graph yields the distinct-substring count. algorithms