CODEWITHSUNDEEP
stringsearchfind
Arash Saidi
Arash Saidi

Reputation: 2238

Boyer Moore Text Algorithm: What happens if needle is one character?

In the Boyer Moore algorithm, when only the bad suffix rule is applied, and we have a needle of one character, does the algorithm compare the character to all the characters in the haystack?

I've tried implementing it, but whenever I use one character I get a nullPointerException as the pointer to the array I have my needle goes to -1. I can't paste the code since it is part of an assignment, and I can't seem to figure out how to solve the issue of searching for one character, so I just implemented a simple brute force search for that case.

Upvotes: 0

Views: 77

Answers (1)

cHao
cHao

Reputation: 86545

If the pattern consists of one character, the algorithm has no choice but to check each character til it finds a match.

Consider what happens when you search for a one-character pattern. You start by checking at the first possible location where the last character of the pattern could match (0), and wherever the string doesn't match, there's no matching suffix -- so you don't have enough info to disqualify the next character as a potential part of the match.

Upvotes: 1

Related Questions