https cpalgorithms comstringzfunction html zfunction or z algorithm efficient algorithm for pattern occurrence in a string time complexity on where n is the length of the string 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 zfunctionabracadabra 0 0 0 1 0 1 0 4 0 0 1 zfunctionaaaa 0 3 2 1 zfunctionzxxzxxz 0 0 0 4 0 0 1 initialize interval s left pointer and right pointer case when current index is inside the interval if new index s result gives us more right interval we ve to update leftpointer and rightpointer check if we have to move forward to the next characters or not example of using zfunction for pattern occurrence given function returns the number of times pattern appears in inputstr as a substring findpatternabr abracadabra 2 findpatterna aaaa 4 findpatternxz zxxzxxz 2 concatenate pattern and inputstr and call zfunction with concatenated string 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 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 initialize interval s left pointer and right pointer case when current index is inside the interval if new index s result gives us more right interval we ve to update left_pointer and right_pointer check if we have to move forward to the next characters or not 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 concatenate pattern and input_str and call z_function with concatenated string 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
def z_function(input_str: str) -> list[int]:
    
    z_result = [0 for i in range(len(input_str))]

    
    left_pointer, right_pointer = 0, 0

    for i in range(1, len(input_str)):
        
        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 i + z_result[i] - 1 > right_pointer:
            left_pointer, right_pointer = i, i + z_result[i] - 1

    return z_result


def go_next(i: int, z_result: list[int], s: str) -> bool:
    
    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:
    
    answer = 0
    
    
    z_result = z_function(pattern + input_str)

    for val in z_result:
        
        
        
        if val >= len(pattern):
            answer += 1

    return answer


if __name__ == "__main__":
    import doctest

    doctest.testmod()