题目描述

对于个长度为 $n$ 的字符串 $s$。定义函数 $z[i]$ 表示 $s$ 和 $s[i,n-1]$（即以 $s[i]$ 开头的后缀）的最长公共前缀（LCP）的长度。$z$ 被称为 $s$ 的 Z 函数。特别地，$z[0] = 0$。

给定字符串 $s$，求 $z$。

输入格式

• $S$

输出格式

• $z_0\, z_1\, z_2 \, \cdots \, z_{|S|-1}$

样例数据

样例 1 输入

abacababacbaacbabbabac

样例 1 输出

0 0 1 0 3 0 4 0 1 0 0 1 1 0 0 2 0 0 4 0 1 0

子任务

$|S| \leq 10^5$ 只包含小写字母。