配点 : 100 点
問題文
N 字符或字符串
按此顺序连接的 X_1, X_2, \dots, X_N 字符串是
它被写为 X_1 + X_2 + \cdots + X_N 。
另外,字符串 X 的 i 从第一个字符开始 j 提取到字符的连续子字符串 X[i,j] 。
为字符串定义汉堡、整个汉堡和半个汉堡,如下所示。这个定义与问题D相同。
- Burger 是一个完整汉堡的字符串,一个半汉堡的字符串。
- 整个汉堡就是汉堡。 A 某些字符 可写为 c ,c + A + c 的字符串和空字符串
- 半个汉堡是不是空的汉堡。 在可以写成 A、B ,A + B 的字符串中,不全是汉堡的字符串
例如,abba 呀
字符串是按顺序排列的字符串,例如 abbcca 都是汉堡,aabb 呀
字符串是按顺序排列的字符串,例如 abbacc 是半个汉堡,abbcbbc 呀
字符串是按顺序排列的字符串,例如 ababa 不是汉堡。
小写英文字母组成的字符串 S 和正整数 请回答以下有关 K 。k = 0, 1, 2, \dots, K 的问题。 一串小写字母,其中
- S[i, j] + T 表示所有汉堡。 T 的最小可能长度是 k 变为 (i, j) (1 \leq i \leq j \leq |S|的数量) 除以 998244353 求余数。
制約
- 1 \leq |S| \leq 200{,}000
- 1 \leq K \leq 200{,}000
- S 是一串小写字母
- K 是一个整数
小課題
-
( 1 点) K \leq 300
-
( 99 点)无附加约束 请输出
入力
输入是按以下格式从标准输入给出的。 请输出超过
S K
出力
K+1 行。
请在
i 输出 k = i-1 时输出答案。
入力例 1
abcc 3
出力例 1
1 5 3 1
S[i,j] + T 变成所有汉堡 T ,T 的最小长度是 k (0 \leq k \leq 3) 变为 每对 (i, j) 如下。 当
- k = 0 时,(3, 4)
- k = 1 时,(1, 1), (2, 2), (3, 3), (4, 4), (2, 4)
- k = 2 时,(1, 2), (2, 3), (1, 4)
- k = 3 时,(1, 3)
S[1, 4] = abcc 是T = ba 会给你所有的汉堡。T 的长度是 1 在以下情况下,它不会是一个完整的汉堡。
该测试用例满足子任务 1 的约束。
入力例 2
fortississimo 7
出力例 2
4 19 20 21 15 8 3 1
该测试用例满足子任务 1 的约束。