题目描述
对于个长度为 n 的字符串 s。定义函数 z[i] 表示 s 和 s[i,n−1](即以 s[i] 开头的后缀)的最长公共前缀(LCP)的长度。z 被称为 s 的 Z 函数。特别地,z[0]=0。
给定字符串 s,求 z。
输入格式
- S
输出格式
- z0z1z2⋯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|≤105 只包含小写字母。