Z 算法（Z Algorithm）

问题描述

给定一个长度为 $N$ 的字符串 $S$（仅含小写英文字母），计算数组 $a_0, a_1, \dots, a_{N-1}$，其中：

• $a_i$ 表示 $S$ 与子串 $S[i:]$ 的最长公共前缀（Longest Common Prefix, LCP）的长度。

即：

$$a_i = \max\{ \ell \ge 0 \mid S[0:\ell) = S[i:i+\ell) \}.$$

约束条件

• $1 \leq N \leq 5 \times 10^5$
• $S$ 仅由小写英文字母组成

输入格式

$S$

输出格式

$a_0\ a_1\ \cdots\ a_{N-1}$

abcbcba

7 0 0 0 0 0 1

mississippi

11 0 0 0 0 0 0 0 0 0 0

ababacaca

9 0 3 0 1 0 1 0 1

aaaaa

5 4 3 2 1