search

TheAlgorithms / Ruby

All algorithms implemented in Ruby
MIT License
1.15k stars 289 forks source link

Implementing `Boyer-Moore-Horspool` substring search algorithm #198

Closed aparibocci closed 1 year ago

aparibocci commented 1 year ago

As per title, this MR aims to add a Ruby implementation of the Boyer-Moore-Horspool algorithm.

This algorithm allows to search occurrences a substring in a given search string using fewer comparison with respect to the "naive" approach of performing left-to-right comparisons for every character in the search string.

Calling n the size of the search string and m the size of the substring pattern, the algorithm runs in O(nm) in the worst case, andO(n) in the average case.

In addition to the function for getting only the first match, one for getting all matches is also provided.

aparibocci commented 1 year ago

Hello @StepfenShawn, could I ask you to have a look at this PR, whenever you have a few minutes? Thank you!