题目描述

XX在进行字符串研究的时候，遇到了一个十分棘手的问题。 在这个问题中，给定一个字符串S，与一个整数K，定义S的子串T=S(i, j)是关于第K位的识别子串，满足以下两个条件： 1、i≤K≤j。 2、子串T只在S中出现过一次。 例如，S="banana"，K=5，则关于第K位的识别子串有"nana"，"anan"，"anana"，"nan"，"banan"和"banana"。 现在，给定S，XX希望知道对于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

f提示 N<=5*10^5

Source