strings.prefix_function

https://cp-algorithms.com/string/prefix-function.html

Prefix function Knuth-Morris-Pratt algorithm

Different algorithm than Knuth-Morris-Pratt pattern finding

E.x. Finding longest prefix which is also suffix

Time Complexity: O(n) - where n is the length of the string

Functions

longest_prefix(→ int)	Prefix-function use case
prefix_function(→ list)	For the given string this function computes value for each index(i),

Module Contents

strings.prefix_function.longest_prefix(input_str: str) → int

Prefix-function use case Finding longest prefix which is suffix as well

>>> longest_prefix("aabcdaabc")
4
>>> longest_prefix("asdasdad")
4
>>> longest_prefix("abcab")
2

strings.prefix_function.prefix_function(input_string: str) → list

For the given string this function computes value for each index(i), which represents the longest coincidence of prefix and suffix for given substring (input_str[0…i])

For the value of the first element the algorithm always returns 0

>>> prefix_function("aabcdaabc")
[0, 1, 0, 0, 0, 1, 2, 3, 4]
>>> prefix_function("asdasdad")
[0, 0, 0, 1, 2, 3, 4, 0]