strings.knuth_morris_pratt
==========================

.. py:module:: strings.knuth_morris_pratt


Attributes
----------

.. autoapisummary::

   strings.knuth_morris_pratt.pattern


Functions
---------

.. autoapisummary::

   strings.knuth_morris_pratt.get_failure_array
   strings.knuth_morris_pratt.knuth_morris_pratt


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

.. py:function:: get_failure_array(pattern: str) -> list[int]

   Calculates the new index we should go to if we fail a comparison
   :param pattern:
   :return:


.. py:function:: knuth_morris_pratt(text: str, pattern: str) -> int

   The Knuth-Morris-Pratt Algorithm for finding a pattern within a piece of text
   with complexity O(n + m)

   1) Preprocess pattern to identify any suffixes that are identical to prefixes

       This tells us where to continue from if we get a mismatch between a character
       in our pattern and the text.

   2) Step through the text one character at a time and compare it to a character in
       the pattern updating our location within the pattern if necessary

   >>> kmp = "knuth_morris_pratt"
   >>> all(
   ...    knuth_morris_pratt(kmp, s) == kmp.find(s)
   ...    for s in ("kn", "h_m", "rr", "tt", "not there")
   ... )
   True


.. py:data:: pattern
   :value: 'abc1abc12'