[Verse 1]
When you're searching through a string for a pattern that you need
Linear scanning takes forever, that's a slow and costly deed
But Boyer-Moore came along with a smarter way to play
Skip ahead when mismatches happen, don't check every single day
Two tables guide the movement, bad character and good suffix
When the pattern doesn't match up, these rules help you get your fix
[Chorus]
Boyer-Moore, skip ahead, don't look back
Bad character, good suffix, stay on track
Right to left we check the pattern
But left to right we slide and happen
Boyer-Moore, Boyer-Moore, skip the noise
Efficient searching is our choice
[Verse 2]
Bad character table tells us how far we can jump ahead
When we hit a mismatch letter, use the table like we said
If the bad char's in our pattern, align it with the text
If it's not there skip the whole thing, move the pattern to what's next
Preprocessing is essential, build the tables before you start
This investment pays dividends when you're searching through the part
[Chorus]
Boyer-Moore, skip ahead, don't look back
Bad character, good suffix, stay on track
Right to left we check the pattern
But left to right we slide and happen
Boyer-Moore, Boyer-Moore, skip the noise
Efficient searching is our choice
[Bridge]
Good suffix rule is trickier but powerful when applied
When a suffix matches perfectly but prefix is denied
Find where that suffix appears again within the pattern's frame
Or find the longest border that can keep us in the game
Maximum of both rules determines how far we can slide
Boyer-Moore beats brute force when we let these tables guide
[Verse 3]
Best case gives us linear time divided by pattern length
When every character mismatches, that's where we show our strength
Worst case still hits quadratic but that's rare in real world use
Preprocessing takes some time but the payoff's no excuse
For text editors and databases, this algorithm's the king
When you need to find patterns fast, Boyer-Moore's the thing
[Chorus]
Boyer-Moore, skip ahead, don't look back
Bad character, good suffix, stay on track
Right to left we check the pattern
But left to right we slide and happen
Boyer-Moore, Boyer-Moore, skip the noise
Efficient searching is our choice
[Outro]
Two tables, right to left check, skip ahead when things go wrong
Boyer-Moore algorithm makes your pattern searching strong