如果一个字符串可以被拆分为
例如,对于字符串 aabaabaa,如果令
一个字符串可能没有优秀的拆分,也可能存在不止一种优秀的拆分。比如我们令
现在给出一个长度为
以下事项需要注意:
- 出现在不同位置的相同子串,我们认为是不同的子串,它们的优秀拆分均会被记入答案。
- 在一个拆分中,允许出现
。例如 cccc 存在拆分 。 - 字符串本身也是它的一个子串。
输入格式
每个输入文件包含多组数据。输入文件的第一行只有一个整数
接下来
输出格式
输出
样例一
input
4 aabbbb cccccc aabaabaabaa bbaabaababaaba
output
3 5 4 7
explanation
我们用
第一组数据中,共有
而剩下的子串不存在优秀的拆分,所以第一组数据的答案是
第二组数据中,有两类,总共
对于子串
对于子串
所以第二组数据的答案是
第三组数据中,
第四组数据中,
样例二
见样例数据下载。
样例三
见样例数据下载。
限制与约定
对于全部的测试点,保证
我们假定
测试点编号 | 其他约束 | |
---|---|---|
1、2 | ||
3、4 | ||
5、6 | 无 | |
7、8 | ||
9、10 | ||
11、12 | ||
13、14 | ||
15 | ||
16 | ||
17 | ||
18 | ||
19 | ||
20 |
时间限制:
空间限制: