← 返回题目列表

Codeforces · 386/C

C. 多样化的子字符串

中文机器翻译题面 查看原题

字符串多样性是指字符串中至少出现一次的符号数量。 s 的多样性用 d(s) 表示。例如,d(“aaa”)=1,d(“abacaba”)=3。

给定一个字符串 s,由小写拉丁字母组成。考虑它的所有子串。显然,任何子串多样性都是从 1 到 d(s) 的数字。查找有关子串多样性的统计数据:对于从 1 到 d(s) 的每个 k,查找 s 有多少个子串的多样性恰好为 k。

输入

输入由包含 s 的单行组成。它仅包含小写拉丁字母,s 的长度为 1 到 3·105。

输出

将值 d(s) 打印到第一行。将序列 t1, t2, ..., td(s) 打印到以下行,其中 ti 是 s 的多样性恰好为 i 的子串的数量。

示例

输入 #1

abca

输出 #1

3
4
3
3

输入 #2

aabacaabbad

输出 #2

4
14
19
28
5

注意

考虑第一个例子。

我们用 s(i, j) 表示“abca”的子串,其索引位于段 [i, j] 中。

- s(1, 1) = “a”, d(“a”) = 1
- s(2, 2) =  "b", d("b") = 1
- s(3, 3) =  "c", d("c") = 1
- s(4, 4) = “a”, d(“a”) = 1
- s(1, 2) =  "ab", d("ab") = 2
- s(2, 3) =  "bc", d("bc") = 2
- s(3, 4) = “ca”, d(“ca”) = 2
- s(1, 3) = “abc”, d(“abc”) = 3
- s(2, 4) = “bca”, d(“bca”) = 3
- s(1, 4) = “abca”, d(“abca”) = 3

多样性 1 的子串总数为 4,多样性 2 等于 3,多样性 3 等于 3。