【模板】扩展 KMP / exKMP（Z 函数）

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

给定两个字符串 $a,b$，请计算两个数组：

• $b$ 的 Z 函数数组 $z$，其中 $z_i$ 是 $b$ 与从位置 $i$ 开始的后缀的最长公共前缀长度；
• 扩展数组 $p$，其中 $p_i$ 是 $b$ 与 $a$ 中从位置 $i$ 开始的后缀的最长公共前缀长度。

数组下标从 $1$ 开始。对于长度为 $n$ 的数组 $x$，定义其权值为

输入格式

第一行包含字符串 $a$，第二行包含字符串 $b$。

两个字符串均非空，且只包含小写英文字母。

输出格式

第一行输出数组 $z$ 的权值。

第二行输出数组 $p$ 的权值。

样例输入 1

aaaabaa
aaaaa

样例输出 1

6
21

样例解释

$z=\{5,4,3,2,1\}$，$p=\{4,3,2,1,0,2,1\}$。

数据范围

对于所有数据，$1\le \lvert a\rvert,\lvert b\rvert\le 2\times10^7$。