[Verse 1]
When patterns hide in massive text domains
Naive search crawls through every single grain
But Donald Knuth conceived a smarter scheme
With Morris-Pratt to optimize the dream
We precompute where failures should retreat
No backtrack wasteland, algorithm's complete
The prefix function maps each mismatch fate
Partial matches guide us, never late
[Chorus]
K-M-P, no restart from zero
Failure function is our searching hero
Longest proper prefix, suffix too
When they match, that's our breakthrough
K-M-P, linear time guarantee
Pattern preprocessing sets us free
Failure function, failure function
Guides us past each malfunction
[Verse 2]
Build the table before the hunt begins
Every position knows where failure wins
If character j won't align today
Jump back to failure-j, that's the way
Pi of i tells the tale we need
How far to leap when matches don't succeed
Border lengths encoded in each slot
Overlap wisdom that we never forgot
[Chorus]
K-M-P, no restart from zero
Failure function is our searching hero
Longest proper prefix, suffix too
When they match, that's our breakthrough
K-M-P, linear time guarantee
Pattern preprocessing sets us free
Failure function, failure function
Guides us past each malfunction
[Bridge]
While brute force stumbles backward through the mire
KMP slides forward, never tire
Two pointers dance across the string
One never drops, efficiency's king
O of m plus n complexity crown
No quadratic nightmare dragging down
[Verse 3]
Text pointer holds its ground steadfast
Pattern pointer may retreat, but fast
When mismatch strikes at position q
Failure function tells us what to do
Jump to failure-q, continue the quest
Proven optimal, algorithm blessed
From ABABA to complex DNA strands
KMP conquers with preprocessing hands
[Outro]
Preprocess pattern, scan text once clean
Most elegant search the world has seen
Failure function, our algorithmic guide
In linear time, we search with pride