链接: https://cses.fi/problemset/task/2107

板块: String Algorithms

时限: 1.00 s ｜ 内存: 512 MB

题目描述

我们考虑一个由 $n$ 个字符组成的字符串，下标为 $1,2,\dots,n$。你的任务是计算下列函数的所有取值：

• $z(i)$ 表示以位置 $i$ 开始、且为字符串前缀的子串的最大长度。此外，$z(1)=0$。
• $\pi(i)$ 表示以位置 $i$ 结束、为字符串前缀、且长度至多为 $i-1$ 的子串的最大长度。

注意，函数 $z$ 用于 Z 算法，函数 $\pi$ 用于 KMP 算法。

输入

唯一的一行输入包含一个长度为 $n$ 的字符串。每个字符均为 a–z 之间。

输出

输出两行：第一行为 $z$ 函数的取值，第二行为 $\pi$ 函数的取值。

数据范围

$1 \le n \le 10^6$

样例输入

abaabca

样例输出

0 0 1 2 0 0 1
0 0 1 1 2 0 1