Boyer–Moore–Horspool algorithm

The algorithm trades space for time in order to obtain an average-case complexity of O(n) on random text, although it has O(nm) in the worst case, where the length of the pattern is m and the length of the search string is n. Like Boyer–Moore, Boyer–Moore–Horspool preprocesses the pattern to produce a table containing, for each symbol in the alphabet, the number of characters that can safely be skipped.

The worst case behavior happens when the bad character skip is consistently low (with the lower limit of 1 byte movement) and a large portion of the needle matches the haystack.

The algorithm enters the full loop only when the check passes:[2] It is unclear whether this 1992 tuning still holds its performance advantage on modern machines.

It appears that Raita is not aware of the old last-character precheck (he believed that the backward-only same routine is the Horspool implementation), so readers are advised to take the results with a grain of salt.

The behavior of an "SFC" loop (Horspool's terminology) both in libstdc++ and libc++ seems to suggest that a modern Raita implementation should not include any of the one-character shifts, since they have detrimental effects on data alignment.