[Verse 1]
Got a pattern to find in a massive text string
Brute force gonna leave you suffering
Check every position, start from the beginning
When mismatch hits, slide one and keep spinning
But that's inefficient, time complexity's rough
O of n times m, man that's way too tough
KMP algorithm came to save the day
Preprocessing patterns in a smarter way
[Chorus]
Failure function, prefix table too
When mismatch hits, know where to jump to
Don't restart from scratch, that's what losers do
KMP keeps it smooth, linear time breakthrough
Build the table first, then search with flow
When patterns don't match, the table will show
How far to jump back, never start from zero
KMP algorithm, computer science hero
[Verse 2]
First phase is building that failure array
For every position, longest prefix that stays
Equal to suffix, but not the whole string
This preprocessing is the powerful thing
Start with zero, then compare and grow
When characters match, increment and go
When they don't match, jump back in the table
Find the next best spot that keeps you stable
[Chorus]
Failure function, prefix table too
When mismatch hits, know where to jump to
Don't restart from scratch, that's what losers do
KMP keeps it smooth, linear time breakthrough
Build the table first, then search with flow
When patterns don't match, the table will show
How far to jump back, never start from zero
KMP algorithm, computer science hero
[Verse 3]
Now searching phase with pattern and text
Use that table to know what comes next
When characters match, advance both pointers
When they don't match, let the table join us
Jump the pattern back but keep text position
That's the magic of this smart transition
No redundant work, no wasted cycles
Linear time complexity, breaking the cycle
[Bridge]
A-B-A-B-A pattern gets tricky to track
Without the table you'd keep sliding back
But failure function shows you the way
Skip ahead smart, save time every day
Preprocessing pays off in the searching game
KMP efficiency putting brute force to shame
[Outro]
From Don Knuth to Morris and Pratt
Brilliant minds that delivered the facts
String matching mastered with elegant code
KMP algorithm, the efficient road
Linear time searching, that's how we roll
Pattern matching perfection, reaching the goal