String Functions

题目描述

我们考虑一个长度为 n 的字符串，位置索引为 1,2,$\dots$,n。你的任务是计算下列函数的所有值： 注意函数 z 用于 Z-算法，函数 $\pi$ 用于 KMP 算法。

输入格式

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

输出格式

输出两行：第一行是 z 函数的各个值，第二行是 $\pi$ 函数的各个值。

abaabca

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

提示

$1 \le n \le 10^6$

标签: CSES2107|字符串

来源

CSES2107|字符串