strings.z_function

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

Z-function or Z algorithm

Efficient algorithm for pattern occurrence in a string

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

Functions

find_pattern(→ int)	Example of using z-function for pattern occurrence
go_next(→ bool)	Check if we have to move forward to the next characters or not
z_function(→ list[int])	For the given string this function computes value for each index,

Module Contents

strings.z_function.find_pattern(pattern: str, input_str: str) → int

Example of using z-function for pattern occurrence Given function returns the number of times ‘pattern’ appears in ‘input_str’ as a substring

>>> find_pattern("abr", "abracadabra")
2
>>> find_pattern("a", "aaaa")
4
>>> find_pattern("xz", "zxxzxxz")
2

strings.z_function.go_next(i: int, z_result: list[int], s: str) → bool

Check if we have to move forward to the next characters or not

strings.z_function.z_function(input_str: str) → list[int]

For the given string this function computes value for each index, which represents the maximal length substring starting from the index and is the same as the prefix of the same size

e.x. for string ‘abab’ for second index value would be 2

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

>>> z_function("abracadabra")
[0, 0, 0, 1, 0, 1, 0, 4, 0, 0, 1]
>>> z_function("aaaa")
[0, 3, 2, 1]
>>> z_function("zxxzxxz")
[0, 0, 0, 4, 0, 0, 1]