题目描述

一般地，对于一个字符串 $S$ 与 $S$ 中第 $i$ 个字符 $x$，定义子串 $T=S[l...r]$ 为一个关于 $x$ 的识别子串，当且仅当：

1. $i\in[l,r]$；
2. $T$ 在 $S$ 中只出现一次。

比如，对于 banana 的第 $5$ 个字符，nana，anan，anana，nan，banan 和 banana 都是关于它的识别子串。

请你写一个程序，计算出对于一个字符串 $S$，关于 $S$ 的每一位最短识别子串的长度。

输入格式

一行一个字符串 $S$。

输出格式

$|S|$ 行，第 $i$ 行一个整数表示 $S_i$ 对应的答案。

agoodcookcooksgoodfood

1
2
3
3
2
2
3
3
2
2
3
3
2
1
2
3
3
2
1
2
3
4

数据规模与约定

对于 $100\%$ 的数据，$|S|\leq 10^5$。