KMP builds a "failure function" to skip re-comparisons on a pattern mismatch, giving O(n+m) string matching. Rabin-Karp uses a rolling hash for O(n+m) average-case matching, useful for multi-pattern search. Manacher's algorithm finds the longest palindromic substring in O(n) by exploiting palindrome symmetry — the optimal way to solve the problem already listed under LCS and String DP.
Sub-patterns
- A — KMP. Failure-function-based pattern matching in O(n+m).
- B — Rabin-Karp. Rolling-hash pattern matching.
- C — Manacher's Algorithm. O(n) longest palindromic substring.
Practice set (4)
- Easy — Find the Index of the First Occurrence in a String
- Medium — Repeated String Match
- Hard — Shortest Palindrome, Longest Duplicate Substring
Pending
KMP
Builds a failure function to skip re-comparisons on a pattern mismatch, giving O(n+m) string matching.
Pending
Rabin-Karp
Rolling-hash pattern matching, useful for multi-pattern search.
Pending
Manacher's Algorithm
Finds the longest palindromic substring in O(n) by exploiting palindrome symmetry.
Notes from readers
Comments — via GitHub