P5410 【模板】扩展 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)$。

输入格式

输出格式

说明/提示

**样例解释:** $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$,所有字符均为小写字母。