4 lessons
String Pattern Matching, From Brute Force Up
Find a word inside a much bigger text, starting from the obvious approach and seeing exactly where it wastes time.
Rolling Hash and the Rabin-Karp Algorithm
Turn a whole substring into one number, update that number in O(1) as the window slides, and compare numbers instead of characters.
The KMP Algorithm
Never re-check a character you have already matched. One precomputed table turns pattern matching into a guaranteed O(n + m).
Manacher's Algorithm for Palindromes
Find the longest palindromic substring in linear time, by reusing palindromes you have already discovered instead of checking each centre from scratch.