
# 「文字列Sを0番目からとi番目から同時に見ていった時に、最大で何文字一致しているか」を記録した配列
# iが0のときはlen(S)が入る
def z_algorithm(s):
    n = len(s)
    z = [0] * n
    z[0] = n
    i = 1
    j = 0
    while i < n:
        while i + j < n and s[j] == s[i + j]:
            j += 1
        z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < n and k + z[k] < j:
            z[i + k] = z[k]
            k += 1
        i += k
        j -= k
    return z
