Skip to content

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

New issue

Have a question about this project? # for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “#”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? # to your account

Open
Duckmolemore opened this issue Apr 8, 2021 · 0 comments
Open

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

Duckmolemore opened this issue Apr 8, 2021 · 0 comments

Comments

@Duckmolemore
Copy link

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
}
# for free to join this conversation on GitHub. Already have an account? # to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant