1582 articles
Rabin Karp uses a polynomial rolling hash to fingerprint each window of the text and matches against the pattern hash in expected O(n + m) time. Master this and you unlock substring search, plagiarism detection, and the entire family of hash-based string problems.
Manacher finds the longest palindromic substring in O(n) by exploiting palindrome symmetry to skip redundant character comparisons. The same mirror trick that powers the Z algorithm, applied to the palindrome radius array.
Precompute polynomial prefix hashes once in O(n) and answer substring equality queries in O(1) for the lifetime of the string. The Swiss army knife behind longest duplicate substring, longest common substring binary search, and dozens of competitive programming techniques.
A suffix array sorts all suffixes of a string lexicographically. Built in O(n log n) with prefix doubling and paired with the Kasai LCP array, it answers substring search, distinct substring count, and longest repeated substring queries in optimal time.
Find the longest contiguous substring shared by two strings. The DP solution is O(n*m), binary search plus rolling hash gives O((n+m) log min(n,m)) expected, and suffix array plus LCP achieves O((n+m) log(n+m)).