strings.boyer_moore_horspool

Boyer-Moore-Horspool string-search algorithm.

A simplification of the Boyer-Moore algorithm that keeps only the bad-character shift table (Horspool’s variant). It still runs in sub-linear time on average (roughly O(n / m) for random text) while worst case is O(n * m). Memory is O(sigma) where sigma is the size of the alphabet that appears in the pattern.

Reference: https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm

Functions

_build_shift_table(→ dict[str, int])	Build the bad-character shift table for pattern.
boyer_moore_horspool_search(→ int)	Return the index of the first occurrence of pattern in text
boyer_moore_horspool_search_all(→ list[int])	Return every starting index where pattern occurs in text.

Module Contents

strings.boyer_moore_horspool._build_shift_table(pattern: str) → dict[str, int]

Build the bad-character shift table for pattern.

For every character in the pattern except the last one, the table stores the distance from that character to the end of the pattern. Characters that do not appear in the pattern fall back to len(pattern) at lookup time.

>>> _build_shift_table("abcab")
{'a': 1, 'b': 3, 'c': 2}
>>> _build_shift_table("a")
{}
>>> _build_shift_table("")
{}
>>> _build_shift_table("aaaa")
{'a': 1}

strings.boyer_moore_horspool.boyer_moore_horspool_search(text: str, pattern: str) → int

Return the index of the first occurrence of pattern in text or -1 if the pattern does not appear.

An empty pattern matches at position 0 (the same convention used by str.find()).

>>> boyer_moore_horspool_search("ABAAABCD", "ABC")
4
>>> boyer_moore_horspool_search("hello world", "world")
6
>>> boyer_moore_horspool_search("hello world", "Python")
-1
>>> boyer_moore_horspool_search("aaaaa", "aa")
0
>>> boyer_moore_horspool_search("anything", "")
0
>>> boyer_moore_horspool_search("", "x")
-1
>>> sample = "the quick brown fox jumps over the lazy dog"
>>> boyer_moore_horspool_search(sample, "fox") == sample.find("fox")
True
>>> boyer_moore_horspool_search(sample, "cat") == sample.find("cat")
True

strings.boyer_moore_horspool.boyer_moore_horspool_search_all(text: str, pattern: str) → list[int]

Return every starting index where pattern occurs in text.

Overlapping matches are reported (e.g. "aaa" contains "aa" at indices 0 and 1). An empty pattern matches at every position from 0 to len(text) inclusive, mirroring str.find() and re.finditer() conventions.

>>> boyer_moore_horspool_search_all("ababcabab", "ab")
[0, 2, 5, 7]
>>> boyer_moore_horspool_search_all("aaaa", "aa")
[0, 1, 2]
>>> boyer_moore_horspool_search_all("abcdef", "gh")
[]
>>> boyer_moore_horspool_search_all("abc", "")
[0, 1, 2, 3]
>>> boyer_moore_horspool_search_all("", "abc")
[]