strings.boyer_moore_horspool
============================

.. py:module:: strings.boyer_moore_horspool

.. autoapi-nested-parse::

   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
---------

.. autoapisummary::

   strings.boyer_moore_horspool._build_shift_table
   strings.boyer_moore_horspool.boyer_moore_horspool_search
   strings.boyer_moore_horspool.boyer_moore_horspool_search_all


Module Contents
---------------

.. py:function:: _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}


.. py:function:: 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
   :py:meth:`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


.. py:function:: 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
   :py:meth:`str.find` and :py:func:`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")
   []