iframe-proxy | Sunbelt Computer Software

90 lines (66 loc) · 2.46 KB

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
def z_function(input_str: str) -> list:
    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]
    z_result = [0] * len(input_str)
    # initialize interval's left pointer and right pointer
    left_pointer, right_pointer = 0, 0
    for i in range(1, len(input_str)):
        # case when current index is inside the interval
        if i <= right_pointer:
            min_edge = min(right_pointer - i + 1, z_result[i - left_pointer])
            z_result[i] = min_edge
        while go_next(i, z_result, input_str):
            z_result[i] += 1
        # if new index's result gives us more right interval,
        # we've to update left_pointer and right_pointer
        if i + z_result[i] - 1 > right_pointer:
            left_pointer, right_pointer = i, i + z_result[i] - 1
    return z_result
def go_next(i, z_result, s):
    Check if we have to move forward to the next characters or not
    return i + z_result[i] < len(s) and s[z_result[i]] == s[i + z_result[i]]
def 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")
    >>> find_pattern("a", "aaaa")
    >>> find_pattern("xz", "zxxzxxz")
    answer = 0
    # concatenate 'pattern' and 'input_str' and call z_function
    # with concatenated string
    z_result = z_function(pattern + input_str)
    for val in z_result:
        # if value is greater then length of the pattern string
        # that means this index is starting position of substring
        # which is equal to pattern string
        if val >= len(pattern):
            answer += 1
    return answer
if __name__ == "__main__":
    import doctest
    doctest.testmod()

Sunbelt Computer Software

PL/B Language Development and Support

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Sunbelt Computer Software

PL/B Language Development and Support

Uh oh!

FilesExpand file tree

z_function.py

Latest commit

History

z_function.py

File metadata and controls