#2865. 字符串识别

题目描述

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  

数据范围与提示

N<=5*10^5