String Matching

Pattern Search Algorithms

1:00

Four algorithms for finding a pattern in text — naive brute force, KMP with its LPS failure function, Boyer-Moore's right-to-left skip rules, and Rabin-Karp's rolling hash.

By the end, you can

Explain why naive search costs O(n·m) in the worst case and where the wasted work comes from.
Define the LPS (failure function) value at each position of a pattern and compute the full LPS array by hand.
Trace the KMP mismatch recovery: given a mismatch at pattern index j, identify the new j using lps[j-1].
State KMP's time and space complexity and explain why the text pointer never rewinds.
Describe Boyer-Moore's bad-character and good-suffix rules and explain how it achieves sublinear best-case performance.
Explain how Rabin-Karp's rolling hash works and identify the scenario where it outperforms KMP and Boyer-Moore.
Compare the four algorithms on time complexity, space, and practical use cases.

Up next in String Algorithms, Advanced DP & Competitive Techniques