strings.knuth_morris_pratt

Attributes

pattern

Functions

get_failure_array(→ list[int])

Calculates the new index we should go to if we fail a comparison

knuth_morris_pratt(→ int)

The Knuth-Morris-Pratt Algorithm for finding a pattern within a piece of text

Module Contents

strings.knuth_morris_pratt.get_failure_array(pattern: str) → list[int]

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

strings.knuth_morris_pratt.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
strings.knuth_morris_pratt.pattern = 'abc1abc12'