fletcher.algorithms.utils.kmp module

Utility functions for the Knuth Moris Pratt string matching algorithm.

fletcher.algorithms.utils.kmp.append_to_kmp_matching(matched_len: int, character: int, pat: bytes, failure_function: numpy.ndarray) → int

Append a character to a Knuth Moris Pratt matching. This function can be used to search for pat in a text with the KMP algorithm. Parameters ———- matched_len: int

The length of the previous maximum prefix of pat that was a suffix of the text. Must sattisfy 0 <= matched_len < len(pat).

character: int

The next character of the text.

pat: bytes

The pattern that is searched in the text.

failure_function: np.ndarray

The KMP failure function of pat. Should be obtained through compute_kmp_failure_function(pat).


The length of the maximum prefix of pat that is a suffix of the text after appendng character. Always => 0 and <= min(matched_len + 1, len(pat)).

fletcher.algorithms.utils.kmp.compute_kmp_failure_function(pat: bytes) → numpy.ndarray

Compute the Knuth Moris Pratt failure function. Parameters ———- pat : bytes

The bytes representation of the string for which to compute the KMP failure function.

Numpy array f of len(pat) + 1 integers.

f[0] = -1. For i > 0, f[i] is equal to the length of the longest propper suffix of pat[:i] that is a prefix of pat. Since, only propper suffixes are considered, for i > 0 we have 0 <= f[i] < i.

>>> comp