#P2865. 字符串识别

    ID: 1978 传统题 1000ms 128MiB 尝试: 888 已通过: 203 难度: 7 上传者: 标签>CF2200提高+/省选-后缀数组倍增计数排序Kasai 算法扫描线二叉堆懒删除

字符串识别

题目描述

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

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

  1. i≤k≤ji\leq k\leq j​;
  2. 子串 TT 只在 SS 中出现过一次。

例如,S=S = banana,k=5k = 5,则关于第 kk 位的识别子串有 nana,anan,anana,nan,banan 和 banana。

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

输入格式

仅一行,输入长度为 nn 的字符串 SS。

输出格式

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

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

数据规模与约定

对于 100%100\%​ 的数据,1≤n≤5×1051\leq n\leq 5\times 10^5。