#P5446. [THUPC2018] 绿绿和串串

[THUPC2018] 绿绿和串串

题目背景

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

题目描述

绿绿有一个由小写字母组成的非空字符串 RR,但 Yazid 不知道它具体是什么。

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

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

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

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

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

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

  • 对于一个串 SSS\left| S\right| 表示的是该串的长度。
  • 对于一个串 SS,我们定义串 TT 是它的前缀,当且仅当 TS\left| T\right|\leq\left| S\right|,且对于任意整数 ii 满足 1iT1\leq i\leq\left| T\right|,都有 TT 的左起第 ii 个字符与 SS 的左起第 ii 个字符相同。(形象地理解,即 TTSS 的前部出现)
    • 如:abcabcdefg的前缀,abaabba的前缀,zz的前缀,空串为任意一个串的前缀。

输入格式

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

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

输出格式

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

  • 从小到大输出 R\left| R\right| 的所有不超过 S\left| S\right| 的可能值,所有值之间用单个空格隔开。
4
abcdcb
qwqwq
qaqaqqq
carnation
4 6
2 3 4 5
6 7
9

提示

数据范围

保证 S106\left| S\right|\leq 10^6S5×106\sum\left| S\right|\leq 5\times 10^6

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

提示

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

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

版权信息

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

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