search

dwnusbaum / boyer-moore-demo

Interactive demo of the Boyer-Moore string search algorithm
https://dwnusbaum.github.io/boyer-moore-demo/
MIT License
8 stars 3 forks source link

The algorithm implementation does not work in the demo page #1

Closed RalphPastel972 closed 4 years ago

RalphPastel972 commented 4 years ago

Hi,

If you go to the demo page (https://dwnusbaum.github.io/boyer-moore-demo/) and use the following Haystack and Needle, the string Ralph is not found:

Haystack: Maisss où est donc Ralph Pastel ? Needle: Ralph

The reason IMO is the fact that there is an issue in the Bad Character Table (5 instead of 4)

dwnusbaum commented 4 years ago

@RalphPastel972 Thanks for the heads up! I think this is a classic JS issue 😓. This code treats a value of 0 for the key as false, when it was intended to be treated as true:

https://github.com/dwnusbaum/boyer-moore-demo/blob/f9f116082e5c8763f6d0ee78d83376fe0bfd9e7c/src/boyerMoore.ts#L101

That causes the value of the bad character table for first character to use the return needle.length branch (5, incorrect) instead of the return needle.length - 1 - rightmostIndex[badChar] branch (4, correct).

The problematic code should probably be changed to something like this:

if (rightmostIndex.hasOwnProperty(badChar)) {

Really, the code should probably use a Map instead of a raw object.

dwnusbaum commented 4 years ago

Should be fixed by c708d4089ce323d1f4b61c2c83dfa1bbf2de8e04.