QOJ.ac

QOJ

Time Limit: 0.2 s Memory Limit: 512 MB
[+8]

# 786. Z 函数

Statistics

题目描述

对于个长度为 n 的字符串 s。定义函数 z[i] 表示 ss[i,n1](即以 s[i] 开头的后缀)的最长公共前缀(LCP)的长度。z 被称为 sZ 函数。特别地,z[0]=0

给定字符串 s,求 z

输入格式

  • S

输出格式

  • z0z1z2z|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 只包含小写字母。