kodecocodes / swift-algorithm-club

Algorithms and data structures in Swift, with explanations!
MIT License
28.85k stars 5k forks source link

About Boyer-Moore-Horspool , are there some mistakes? #972

Open Duckmolemore opened 3 years ago

Duckmolemore commented 3 years ago

Brief Intro

To me, Boyer-Moore and Boyer-Moore-Horspool make no difference, they both skip one character ahead. Because max(skipTable[c] ?? patternLength, 1) will always be 1 (skipTable[c] == skipTable[lastChar] == 0). Should skipTable exclude pattern's lastChar? Or am I misunderstand something?

More Details

// Make the skip table. This table determines how far we skip ahead
// when a character from the pattern is found.
var skipTable = [Character: Int]()
for (i, c) in pattern.enumerated() {
    skipTable[c] = patternLength - i - 1
}

if !usingHorspoolImprovement {
    // If no match, we can only safely skip one character ahead.
    i = index(after: i)
} else {
    // Ensure to jump at least one character (this is needed because the first
    // character is in the skipTable, and `skipTable[lastChar] = 0`)
    let jumpOffset = max(skipTable[c] ?? patternLength, 1)
    i = index(i, offsetBy: jumpOffset, limitedBy: endIndex) ?? endIndex
}