Strings

Searching text and indexing it: naive matching, Rabin-Karp, Knuth-Morris-Pratt, Boyer-Moore, tries and suffix arrays, each traced character by character and compared with what Python's own string search does.

This part builds on Hashing and Algorithm design.

1 of 4 topics ready, listed in reading order

String matchingNaive matching, Rabin-Karp rolling hashes, string-matching automata and the Knuth-Morris-Pratt failure function.Ready

Boyer-Moore searchThe bad character and good suffix rules, Horspool's simplification and why long patterns search faster.Planned

TriesTries and compressed tries for prefix search, autocomplete and dictionary matching.Planned

Suffix arraysBuilding suffix arrays, the longest common prefix array and the queries they answer.Planned