Knuth–Morris–Pratt (KMP) — Visual Guide
Step through the algorithm to see why it runs in
O(n)
.
Python Reference Implementation
kmp_search() — live highlighted
Text (haystack)
Pattern (needle)
Build LPS (π) Table
◀ Prev
Step ▶
Auto Play
Reset
Speed
Text
Pattern
LPS / Prefix Function π (for pattern)
Narration
Click
Build LPS
to compute the prefix table, then use
Step
or
Auto Play
to run KMP.