[Verse 1]
Started with a text and pattern in my hand
Naive approach was moving left to right so bland
Character by character checking every spot
But Boyer-Moore came through when efficiency was hot
Two tables precomputed before we even start
Bad character table playing the smartest part
When mismatch hits we slide that pattern right
Skip the useless checks and keep our search tight
[Chorus]
Boyer-Moore scanning right to left direction
Bad character good suffix for protection
Preprocessing tables guide us where to slide
Maximum distance keeps efficiency our pride
Scan right shift smart that's the Boyer way
Linear time average that's how we play
[Verse 2]
Good suffix table handling repetition clean
When partial match breaks down it maps the scene
If suffix reappears somewhere before the end
We know exactly where that pattern ought to bend
Preprocessing phase takes order M time flat
Where M is pattern length and that's a fact
But searching through the text runs super fast
Sublinear performance unsurpassed
[Chorus]
Boyer-Moore scanning right to left direction
Bad character good suffix for protection
Preprocessing tables guide us where to slide
Maximum distance keeps efficiency our pride
Scan right shift smart that's the Boyer way
Linear time average that's how we play
[Bridge]
Right to left scanning seems backwards but it's wise
Mismatches early help us maximize
The distance that we jump when characters don't align
Bad character heuristic keeps us in line
Good suffix heuristic handles pattern repeats
Two tables working together can't be beat
[Verse 3]
Worst case scenario still hits quadratic time
When pathological cases mess up our rhyme
But average case performance runs so clean
Best string searching algorithm ever seen
Industry standard for text processing tools
Boyer-Moore algorithm breaking all the rules
From text editors to database search systems
This algorithm solves em with precision
[Chorus]
Boyer-Moore scanning right to left direction
Bad character good suffix for protection
Preprocessing tables guide us where to slide
Maximum distance keeps efficiency our pride
Scan right shift smart that's the Boyer way
Linear time average that's how we play
[Outro]
Two tables preprocessing maximum shift distance
Boyer-Moore forever showing search resistance
Right to left scanning with intelligent slides
That's how this algorithm efficiently rides