Diverse Substrings

题意翻译

### 题目描述 给定一个字符串 $s$，定义 $d(x)$ 为字符串 $x$ 内不同的字符个数。 求有多少个 $s$ 的子串 $s1$，使得 $d(s1)$ 为给定的 $t_{i}$。 ### 输入格式 第一行包含一个字符串 $s$。 ### 输出格式 第一行输出 $d(s)$。 然后输出 $t_1,t_2,\cdots,t_{d(s)}$ 对应的子串数量。 $1 \le |s| \le 3 \times 10^5$。

题目描述

String diversity is the number of symbols that occur in the string at least once. Diversity of $ s $ will be denoted by $ d(s) $ . For example , $ d $ ("aaa")=1, $ d $ ("abacaba")=3. Given a string $ s $ , consisting of lowercase Latin letters. Consider all its substrings. Obviously, any substring diversity is a number from 1 to $ d(s) $ . Find statistics about substrings diversity: for each $ k $ from 1 to $ d(s) $ , find how many substrings of $ s $ has a diversity of exactly $ k $ .

输入输出格式

输入格式

The input consists of a single line containing $ s $ . It contains only lowercase Latin letters, the length of $ s $ is from 1 to $ 3·10^{5} $ .

输出格式

Print to the first line the value $ d(s) $ . Print sequence $ t_{1},t_{2},...,t_{d(s)} $ to the following lines, where $ t_{i} $ is the number of substrings of $ s $ having diversity of exactly $ i $ .

输入输出样例

输入样例 #1

abca

输出样例 #1

3
4
3
3

输入样例 #2

aabacaabbad

输出样例 #2

4
14
19
28
5

说明

Consider the first example. We denote by $ s(i,j) $ a substring of "abca" with the indices in the segment $ [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 $ Total number of substring with diversity 1 is 4, with diversity 2 equals 3, 3 diversity is 3.