#CS2107. 字符串函数

字符串函数

题目背景

翻译自 CSES-2107 题。

题目描述

给定一个长度为 n 的字符串，字符串的索引为 1,2,…,n1, 2, \dots, n1,2,…,n。你的任务是计算以下两个函数的所有值：

• z(i) z(i) z(i)：表示从位置 i i i 开始的最大子串长度，该子串是字符串的前缀。此外，z(1)=0z(1) = 0z(1)=0。

• π(i) \pi(i) π(i)：表示以位置 i i i 结尾的最大子串长度，该子串是字符串的前缀，且长度不超过 i−1i-1i−1。

注意：

• z z z 函数在 Z 算法中使用。

• π \pi π 函数在 KMPKMPKMP 算法中使用。

输入格式

唯一的一行输入包含一个长度为 n 的字符串，字符串中的字符是小写字母 a–za–za–z。

输出格式

输出两行：

• 第一行输出 z 函数的值。

• 第二行输出 π\piπ 函数的值。

样例

abaabca

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

说明/提示

1≤n≤106。