[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
← Levenshtein distance (edit distance) | Longest common subsequence →