字符串识别

时间限制:10s      空间限制:128MB

题目描述

XX在进行字符串研究的时候,遇到了一个十分棘手的问题。

在这个问题中,给定一个字符串S,与一个整数K,定义S的子串T=S(i, j)是关于第K位的识别子串,满足以下两个条件:

1、iKj

2、子串T只在S中出现过一次。

例如,S="banana"K=5,则关于第K位的识别子串有"nana""anan""anana""nan""banan""banana"

现在,给定SXX希望知道对于S的每一位,最短的识别子串长度是多少,请你来帮助他。


输入格式

仅一行,输入长度为N的字符串S


输出格式

输出N行,每行一个整数,第i行的整数表示对于第i位的最短识别子串长度。


样例输入

agoodcookcooksgoodfood


样例输出

1

2

3

3

2

2

3

3

2

2

3

3

2

1

2

3

3

2

1

2

3

4

提示

N<=5*10^5


题目来源

没有写明来源