题目描述

给定一个字符串 $t$，求出 $t$ 每一个前缀的最大真前缀与真后缀匹配长度。

例如，字符串 ababad 每一位的最大前后缀匹配长度为：

• a：$0$
• ab：$0$
• aba：$1$（a 与 a）
• abab：$2$（ab 与 ab）
• ababa：$3$（aba 与 aba）
• ababad：$0$

输入格式

输入一行一个字符串 $t$。

输出格式

输出 $|t|$ 行，第 $i$ 行表示 $t$ 的前 $i$ 个字符组成的前缀的最大真前缀与真后缀匹配长度。

ababad

0
0
1
2
3
0

数据范围与提示

• $1 \le |t| \le 10^6$。

• 来源：KMP