Pattern matching from naive scans to KMP failure functions and rolling hashes.
5 visualizations
Tries the pattern at every text position, comparing character by character — simple but O(nm).
Precomputes a failure function so mismatches skip ahead without ever re-scanning text — O(n + m).
Hashes each text window and only compares characters when hashes collide — average O(n + m).
Computes for every position the longest match with the string's own prefix (Z-array) in O(n), finding all pattern occurrences.
Compares the pattern right-to-left and uses the bad-character rule to skip large chunks of text — often sublinear in practice.