KMP Algorithm Visualizer

What is KMP Algorithm Visualizer?

KMP Algorithm Visualizer animates Knuth-Morris-Pratt string matching in the two phases it actually has: first the failure table (also called the prefix function or LPS array) is built from the pattern alone, then the search runs using that table to slide the pattern on a mismatch. The insight worth seeing rather than reading is that the text pointer never moves backward — a mismatch reuses what you already matched instead of restarting, which is where the O(n + m) guarantee comes from.

Recommended workflow

1. 1

   Compare with rolling-hash matching

   Rabin-Karp hashes windows instead of preprocessing the pattern.

   Open tool
2. 2

   See 30+ more algorithms animated

   String matching, DP, graphs and backtracking in one player.

   Open tool

Frequently asked questions

What exactly does the failure table store?

For each position i in the pattern, the length of the longest proper prefix of pattern[0..i] that is also a suffix of it. That length tells you how much of a partial match is still usable after a mismatch.

Why is KMP O(n + m)?

The failure table costs O(m) to build, and during the search the text pointer only advances — never backtracks — so the search is O(n). Together that is O(n + m).

Is the failure table the same as the LPS array?

Yes. LPS stands for Longest Prefix which is also Suffix; different textbooks call the same array the failure function, the prefix function, or the LPS array.

When is naive matching good enough?

Most of the time, on short patterns and ordinary text. KMP's advantage shows on adversarial input with lots of repeated prefixes, like searching "aaaab" inside a long run of a's.