0

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.

0

1 Answer 1

1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.