#P1396. 识别子串

    ID: 408 传统题 1000ms 512MiB 尝试: 1036 已通过: 477 难度: 7 上传者: 标签>CF2300提高+/省选-后缀数组倍增计数排序Kasai 算法扫描线二叉堆懒删除前后缀最值

识别子串

题目描述

一般地,对于一个字符串 SS 与 SS 中第 ii 个字符 xx,定义子串 T=S[l...r]T=S[l...r] 为一个关于 xx 的识别子串,当且仅当:

  1. i∈[l,r]i\in[l,r];
  2. TT 在 SS 中只出现一次。

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

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

输入格式

一行一个字符串 SS。

输出格式

∣S∣|S| 行,第 ii 行一个整数表示 SiS_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%100\% 的数据,∣S∣≤105|S|\leq 10^5。