CF827E Rusty String

Grigory 喜欢字符串。最近他在阁楼上发现了一根金属条，这根金属条长度为 $n$，由字母 “V” 和 “K” 组成。不幸的是，一些字母已经被锈蚀，导致现在无法辨认这些位置上写的是什么字母。 Grigory 长时间想不出来这些字母让他联想起什么，于是他对以下问题产生了兴趣：如果每个无法辨认的位置都填入字母 “V” 或 “K”，那么这样得到的字符串可能的周期有哪些？ 字符串的周期是一个整数 $d$（$1$ 到字符串长度），使得当我们将字符串整体右移 $d$ 个位置后与原字符串重叠时，所有重叠位置上的字母都相同。例如，“VKKVK” 的周期有 $3$ 和 $5$。

输入包含若干（至少一组）测试用例。第一行包含一个整数，表示测试用例的个数。 每个测试用例之前有一个空行。每个测试用例由两行描述：第一行一个整数 $n$（$1\leq n\leq 5\cdot 10^{5}$），表示字符串长度。第二行为一个长度为 $n$ 的字符串，仅包含字母 “V”、“K” 和字符 “?”，其中 “?” 表示该位置的字母已无法辨认。 保证所有测试用例中字符串长度之和不超过 $5\cdot 10^{5}$。 对于 hack，您只能使用只有一个测试用例的数据。

对于每个测试用例，输出两行。第一行输出可行周期数。第二行输出这些周期的所有取值，按升序排列。

第一个示例中，我们可以构造出 “VKKVK”，其周期有 $3$ 和 $5$。 第二个示例中，我们可以得到 “VVVVVV”，它的所有周期为 $1$ 到 $6$。 第三个示例中，字符串 “KVKV” 有周期 $2$ 和 $4$，“KVKK” 有周期 $3$ 和 $4$。 由 ChatGPT 5 翻译