[Verse 1]
Substring matching got you twisted up in knots
Brute force checking every single character spot
But Rabin-Karp rolls with polynomial hash
Computing fingerprints lightning fast
Take your pattern, give it numeric weight
Rolling hash means we don't have to wait
Slide the window, update on the fly
Subtract the left, add right side
[Chorus]
Hash it once, then roll it smooth
Polynomial base keeps the groove
When the fingerprints align
Check character by character line
Rolling hash, rolling hash
Amortized speed, linear dash
Rabin-Karp, the searching king
Probabilistic matching
[Verse 2]
Pick a prime number, modulo math
Keeps the hash values on the narrow path
Base raised to power, weighted sum
Each position's contribution
Spurious hits might fool the test
False positives need double check
Hash collision doesn't mean we're done
Verify each match one by one
[Chorus]
Hash it once, then roll it smooth
Polynomial base keeps the groove
When the fingerprints align
Check character by character line
Rolling hash, rolling hash
Amortized speed, linear dash
Rabin-Karp, the searching king
Probabilistic matching
[Bridge]
Precompute the highest power
Save yourself computational hour
Sliding window mathematics
Elegance in string dramatics
Expected time complexity
Linear probability
Worst case quadratic doom
But average case makes room
[Verse 3]
Text length n, pattern length m
Rolling hash breaks the tedium
Multiple patterns, search them all
Hash table answers every call
DNA sequences, plagiarism detection
Rabin-Karp provides protection
Fingerprinting documents clean
Most efficient search machine
[Chorus]
Hash it once, then roll it smooth
Polynomial base keeps the groove
When the fingerprints align
Check character by character line
Rolling hash, rolling hash
Amortized speed, linear dash
Rabin-Karp, the searching king
Probabilistic matching
[Outro]
Monte Carlo randomization
Guarantees approximation
When you need that substring found
Rabin-Karp comes rolling round