Begin Algo
Algorithms · 6 lessons

String AlgorithmsMatching, searching and hashing

Brute-force string matching is O(nm) in the worst case. Every algorithm in this topic avoids re-comparing in a different way: hashing replaces strings with numbers, KMP and Z reuse what has already been matched, and Manacher exploits the symmetry of palindromes.

Why learn String Algorithms

Where it shows up
Ctrl+F and grep

Finding a string in a hundred-million-character log is O(nm) at worst by brute force. KMP never re-reads what it has already matched, making it linear.

→ Lesson: KMP
Plagiarism and duplicate detection

Hash each passage to a number and compare numbers instead of text. Rabin-Karp's rolling hash means sliding the window costs nothing.

→ Lesson: Rabin-Karp
DNA sequence analysis

A genome is a very long ACGT string. Finding a particular fragment, or a palindromic structure (restriction sites often are), is string algorithms.

→ Lesson: String Hashing
Matching thousands of keywords at once

A trie layers every keyword on top of each other, so one pass over the document finds all of them.

→ Lesson: Trie Applications

Lessons

6 lessons
#AlgorithmDifficulty
01String Hashing String hashingPolynomial hashing, the modulus, and collisionsUsed for: Comparing substrings for equality quickly02Rabin-Karp Rolling hash matchingUpdate the hash in O(1) as the window movesUsed for: Plagiarism detection, multi-pattern matching03KMP Prefix-function matchingThe failure function keeps the match pointer from going backwardsUsed for: Text search, signature matching in intrusion detection04Z-Algorithm The Z functionFor each position, the longest common prefix with the whole stringUsed for: String matching, detecting periodicity05Manacher Longest palindromeReuse the symmetry of known palindromes instead of expanding againUsed for: Palindromic DNA fragments, text analysis06Trie Applications Tries in practiceAutocomplete, Word Search II, multi-pattern matchingUsed for: Search suggestions, profanity filtering