[Verse 1]
Pattern matching was a nightmare, brute force taking years
Checking every single position, complexity brings tears
But Knuth and Morris-Pratt discovered preprocessing magic
Build a table, skip ahead, make searches less tragic
The failure function maps each prefix, longest proper match
When mismatch hits, don't restart, just consult your batch
[Chorus]
K-M-P, preprocess the pattern first
Failure function saves the day, quenches searching thirst
Skip the backtrack, jump ahead, partial info stays
Linear time complexity, efficient scanning pays
K-M-P, the smart way to find your needle clean
In the haystack of data, fastest search machine
[Verse 2]
Build your pi table character by character with care
Length of longest prefix that's also suffix there
Start with zero, scan along, when letters disagree
Jump back using previous value, that's the KMP key
The border calculation keeps the useful work intact
Preprocessed intelligence, that's an algorithmic fact
[Chorus]
K-M-P, preprocess the pattern first
Failure function saves the day, quenches searching thirst
Skip the backtrack, jump ahead, partial info stays
Linear time complexity, efficient scanning pays
K-M-P, the smart way to find your needle clean
In the haystack of data, fastest search machine
[Bridge]
Text position never moves backward in this dance
Pattern shifts efficiently, given one more chance
Border lengths unlock the secret, where to resume the fight
O of n plus m runtime, optimization's might
[Verse 3]
Mismatch doesn't mean restart from position one
Use the failure table wisdom, keep the progress won
Partial matches carry forward, information gold
KMP eliminated wasteful scans of days of old
[Chorus]
K-M-P, preprocess the pattern first
Failure function saves the day, quenches searching thirst
Skip the backtrack, jump ahead, partial info stays
Linear time complexity, efficient scanning pays
K-M-P, the smart way to find your needle clean
In the haystack of data, fastest search machine
[Outro]
From naive to optimized, the algorithm evolved
Pattern preprocessing magic, searching problems solved