Z-function (python)

def z_function(s: str) -> list:
    n: int = len(s)
    zf: list = [0 for _ in range(n)]
    for i in range(n):
        while i + zf[i] < n and s[zf[i]] == s[i + zf[i]]:
            zf[i] += 1

    return zf


def effective_z_function(s: str) -> list:
    n: int = len(s)
    left: int = 0
    right: int = 0
    zf: list = [0 for _ in range(n)]
    for i in range(n):
        zf[i] = max(0, min(right - i, zf[i - left]))
        while zf[i] < n and s[zf[i]] == s[i + zf[i]]:
            zf[i] += 1
        if i + zf[i] > right:
            left = i
            right = i + zf[i]

    return zf

def random_string(count: int) -> str:
    return ''.join(random.choice(string.ascii_letters) for _ in range(count))