About Boyer-Moore-Horspool , are there some mistakes?
Duckmolemore opened this issue · 0 comments
Duckmolemore commented
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
}