Z函数

s = input()
n = len(s)
z = [0] * n
left,right = 0,0
# z[i]表示s和s[i:]的LCP长度，规定z[0] = 0！
for i in range(1,n):
    # 如果在z-box里，那么更新它的z[i]的值！
    if i <= right:
        z[i] = min(z[i - left],right - i + 1)
    # 相当于暴力更新
    while i + z[i] < n and s[z[i]] == s[i + z[i]]:
        # 更新 z-box！
        left,right = i,i + z[i]
        z[i] += 1

print(z)