[Verse 1]
String matching problem got you feeling stuck
Brute force searching gonna test your luck
But there's a better way to find your text
Rolling hash technique keeps algorithms flexed
Rabin and Karp they showed us how to roll
Polynomial hashing is the key to our goal
Take each character multiply by base
Modulo keeps the numbers in their place
[Chorus]
Roll the hash roll it right
Sliding window through the night
When the hashes match we found
Something special in the ground
But don't forget the collision test
Compare the strings to be your best
Rolling hash saves us time
Rabin-Karp the paradigm
[Verse 2]
Start with pattern calculate its hash
Then slide through text like lightning flash
Remove the leftmost add the right
Rolling calculation burning bright
Base to the power of pattern length
That's the factor for your hash strength
Subtract old character times the power
Add new character to the tower
[Chorus]
Roll the hash roll it right
Sliding window through the night
When the hashes match we found
Something special in the ground
But don't forget the collision test
Compare the strings to be your best
Rolling hash saves us time
Rabin-Karp the paradigm
[Bridge]
Worst case still takes quadratic time
When every hash collision aligns
But average case is linear flow
That's the beauty that we need to know
Choose your base and modulus wise
Prime numbers help minimize
The chances that false matches appear
Keep your algorithm running clear
[Verse 3]
Multiple patterns no problem here
Rabin-Karp can handle them with cheer
Calculate each pattern hash up front
Then search for all in single hunt
Text preprocessing takes just one pass
Rolling through with polynomial class
Linear expected time complexity
That's string matching efficiency
[Chorus]
Roll the hash roll it right
Sliding window through the night
When the hashes match we found
Something special in the ground
But don't forget the collision test
Compare the strings to be your best
Rolling hash saves us time
Rabin-Karp the paradigm
[Outro]
From text editors to DNA strands
Rabin-Karp algorithm commands
Rolling hash through infinite space
Finding patterns in every place
When you need to search and find
Keep this algorithm in mind
Roll the hash and test with care
Rabin-Karp will get you there