Part VIII · String Algorithms and Text Indexing
49. Suffix Structures and String Indexing
6 lessons•25 topics•Advanced / Expert
0 of 6 lessons published
49.01Outline
Suffix arrays
- Suffix sorting
- Naive construction
- Doubling algorithm
- SA-IS overview
- Rank arrays
49.02Outline
LCP arrays
- Kasai algorithm
- Longest common prefix of adjacent suffixes
- RMQ over LCP
- Distinct substrings
49.03Outline
Suffix trees
- Compressed suffix trie
- Edge labels
- Ukkonen's algorithm overview
- Implicit vs explicit nodes
49.04Outline
Suffix automata
- Endpos equivalence
- States and suffix links
- Online extension
- Count distinct substrings
49.05Outline
FM-index and BWT
- Burrows-Wheeler transform
- Backward search
- Rank/select overview
- Compressed full-text indexing
49.06Outline
Text indexing applications
- Longest repeated substring
- Longest common substring
- Pattern occurrence counting
- Substring lexicographic ordering