302034: CF386C. Diverse Substrings
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
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