字符串多样性是指字符串中至少出现一次的符号数量。 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。