#6387. 「THUPC2018」绿绿与串串 / String

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: diamond_duke

题目描述

绿绿和 Yazid 是好朋友。他们在一起做串串游戏。

我们定义翻转的操作:把一个串以最后一个字符作对称轴进行翻转复制。形式化地描述就是,如果他翻转的串为 R ,那么他会将前 \left| R\right|-1 个字符倒序排列后,插入到串的最后。

举例而言,串abcd进行翻转操作后,将得到abcdcba;串qw连续进行 2 翻转操作后,将得到qwqwq;串z无论进行多少次翻转操作,都不会被改变。

贪玩的绿绿进行了若干次(可能为 0 次)翻转操作。

淘气的绿绿又展示出了一个非空串 S ,并表示 S 最终的串 R 的前缀。现在,他想考考 Yazid,初始的串 R 的长度可能是多少。

Yazid 找到了正在参加清华校赛的你,请你来帮他解决这个问题。但聪明的 Yazid 发现,所有超过 \left| S\right| 的整数都一定是 R 的可能长度,因此你只需要告诉他不超过的 \left| S\right| R 的可能长度即可。

为了帮助你理解问题,Yazid 还将对一些概念和记号做出解释:

  • 对于一个串 S \left| S\right| 表示的是该串的长度。

  • 对于一个串 S ,我们定义串 T 是它的前缀,当且仅当 \left| T\right|\leq\left| S\right| ,且对于任意整数 i 满足 1\leq i\leq\left| T\right| ,都有 T 的左起第 i 个字符与 S 的左起第 i 个字符相同。(形象地理解,即 T S 的前部出现)

  • 如:abcabcdefg的前缀,abaabba的前缀,zz的前缀,空串为任意一个串的前缀。

输入格式

输入包含多组数据,第一行一个整数 T 表示数据组数。接下来依次描述每组数据,对于每组数据:

  • 一行一个仅由小写字母组成的非空字符串 S

输出格式

对于每组数据,输出 1 行:

  • 从小到大输出 \left| R\right| 的所有不超过 \left| S\right| 的可能值,所有值之间用单个空格隔开。

样例

样例输入

4
abcdcb
qwqwq
qaqaqqq
carnation

样例输出

4 6
2 3 4 5
6 7
9

数据范围与提示

保证 \left| S\right|\leq 10^6 \sum\left| S\right|\leq 5\times 10^6

\sum\left| S\right| 表示的是单个测试点中所有数据 \left| S\right| 的总和。

  • 读入规模较大,请注意读入效率。

  • 样例中的最后一个字符串是什么意思呢?

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2018),感谢 Pony.ai 对此次比赛的支持。

题解等资源可在 https://github.com/wangyurzee7/THUPC2018 查看。