substrings_search_zfunc_en.py

def z_function(input_string, result): #memory pre-allocated
    n = len(input_string)
    left,right = 0,0 #we have two pointers which will slide through array, right will always show the border of now-known prefix
    for i in range(1,len(input_string)):
        result[i] = max(0, min(right-i, result[i-left])) #init with known prefix info
        while i + result[i] < n and input_string[result[i]] == input_string[i + result[i]]:
            result[i] += 1 #run to the right to check prefix-equality
        if i + result[i] > right: #if border moved - update left and right
            left = i
            right = i + result[i]
    return

def search_z_func(needle, haystack, z_array):
    z_function(needle+'$'+haystack, z_array) #using symbol '$' as a separator (suppose we have no '$' in text)
    result = []
    n = len(needle)
    for i in range(len(needle), len(z_array)):
        if z_array[i] == n:
            result.append(i - len(needle) - 1) #if we found value of z-func equal to value of needle - save position
    return result