【模板】扩展 KMP/exKMP(Z 函数)

题目描述

给定两个字符串 $a,b$,你要求出两个数组: - $b$ 的 $z$ 函数数组 $z$,即 $b$ 与 $b$ 的每一个后缀的 LCP 长度。 - $b$ 与 $a$ 的每一个后缀的 LCP 长度数组 $p$。 对于一个长度为 $n$ 的数组 $a$,设其权值为 $\operatorname{xor}_{i=1}^n i \times (a_i + 1)$。

输入输出格式

输入格式


两行两个字符串 $a,b$。

输出格式


第一行一个整数,表示 $z$ 的权值。 第二行一个整数,表示 $p$ 的权值。

输入输出样例

输入样例 #1

aaaabaa
aaaaa

输出样例 #1

6
21

说明

**样例解释:** $z = \{5\ 4\ 3\ 2\ 1\}$,$p = \{4\ 3\ 2\ 1\ 0\ 2\ 1\}$。 --- **数据范围:** 对于第一个测试点,$|a|,|b| \le 2 \times 10^3$。 对于第二个测试点,$|a|,|b| \le 2 \times 10^5$。 对于 $100\%$ 的数据,$1 \le |a|,|b| \le 2 \times 10^7$,所有字符均为小写字母。