题意重述

定义一种操作：对于一个字符串 $R$，进行 翻转 操作，得到的新串为

$$R + \text{reverse}(R[1:|R|-1])$$

即：在 $R$ 末尾接上 $R$ 去掉最后一个字符后的反转。

例如：

• abcd → abcdcba
• qw → qwq
• z → z

可以进行若干次（包括 $0$ 次）翻转操作。
给定一个字符串 $S$，已知 $S$ 是最终串 $R'$ 的前缀（$R'$ 是初始串 $R$ 经过若干次翻转得到的）。
问：初始串 $R$ 的长度（$|R|$）的可能值是多少？
只需要输出不超过 $|S|$ 的可能值，因为所有超过 $|S|$ 的整数都是可能的（可以通过在 $R$ 后加足够多的字符再进行翻转使得 $S$ 为前缀）。

---

第一步：分析翻转操作的结构

设 $R = a_1 a_2 \dots a_n$。

一次翻转后：

$$R^{(1)} = a_1 a_2 \dots a_n a_{n-1} \dots a_1$$

长度变为 $2n-1$。

第二次翻转：对 $R^{(1)}$ 进行同样的操作，设 $R^{(1)}$ 长度为 $m$，则新串为 $R^{(1)}$ 接上它的前 $m-1$ 个字符的反转。

我们可以发现，翻转操作后，串总是回文的，并且它的对称中心是原串的最后一个字符。

更精确地，如果初始串 $R$ 长度为 $n$，经过 $k$ 次翻转后得到的串长度是 $n \cdot 2^k - (2^k - 1)$。

但是更关键的是结构上的递归性：

设 $f(R)$ 表示一次翻转后的串。
那么 $f(R)$ 可以看作以 $R$ 的最后一个字符 $a_n$ 为中心的回文串。
$f(f(R))$ 则是以 $f(R)$ 的最后一个字符（即 $a_1$）为中心的回文串，等等。

---

第二步：转化为回文性质

设初始串 $R = a_1 a_2 \dots a_n$。
进行 $t$ 次翻转后得到的串记为 $P_t$。

性质 1：$P_t$ 总是一个回文串。

性质 2：$P_t$ 的中心字符是 $P_{t-1}$ 的第一个字符（当 $t \ge 1$ 时），具体地：

• $P_0 = R$（不回文，除非 $R$ 是回文）。
• $P_1$ 中心是 $a_n$（$R$ 的最后一个字符）。
• $P_2$ 中心是 $a_1$（$R$ 的第一个字符）。
• $P_3$ 中心是 $a_{n-1}$（$R$ 的倒数第二个字符），依此类推。

---

第三步：$S$ 是某个 $P_t$ 的前缀

$S$ 是 $P_t$ 的前缀，这意味着 $S$ 必须满足什么条件？

由于 $P_t$ 是回文串，$S$ 的前 $|S|$ 个字符必须与 $P_t$ 的前 $|S|$ 个字符一致，这给出了对 $S$ 的某些回文约束。

更具体地，我们可以从 $S$ 中推断出 $R$ 的部分字符的对应关系。

设 $R = X$，长度为 $n$。
$P_t$ 的长度 $L_t = n \cdot 2^t - (2^t - 1)$。

如果 $S$ 是 $P_t$ 的前缀，那么 $S$ 必须能写成 $P_t$ 的前缀形式，即 $P_t[1:|S|]$。

---

第四步：对每个可能的 $n$ 判断可行性

由于 $n \le |S|$，我们可以枚举 $n$（初始长度），然后检查是否存在 $t \ge 0$ 使得 $S$ 是 $P_t$ 的前缀。

但直接枚举 $t$ 不可行，因为 $t$ 可能很大。不过 $t$ 每增加 $1$，串长翻倍减 $1$，因此当 $n$ 固定时，$t$ 受限于 $L_t \ge |S|$。

由于 $S$ 是前缀，我们可以用 $S$ 的信息来约束 $R$。

---

关键思路：递归检查

对于固定的 $n$，我们想判断是否存在 $t$ 使得 $S$ 是 $P_t$ 的前缀。

考虑递归过程：
设当前串 $Q$ 是某个 $P_k$，我们已知 $S$ 的前 $|Q|$ 字符与 $Q$ 一致（如果 $|Q| \le |S|$）。

$P_k$ 是回文串，中心是某个字符 $c$（由 $R$ 的某个位置决定）。
$P_{k+1}$ 是 $P_k$ 进行翻转得到的，长度 $2|Q|-1$。

如果 $|S| \le |Q|$，那么我们只需检查 $S$ 是否是 $Q$ 的前缀（且 $Q$ 是某个 $P_k$）。
如果 $|S| > |Q|$，那么 $S$ 的前 $|Q|$ 个字符必须等于 $Q$，并且 $S$ 的剩余部分必须满足 $P_{k+1}$ 的结构。

这提示我们一个递归匹配算法：
从某个初始猜测的 $t$ 开始，但我们可以反过来：给定 $R$，可以直接生成 $P_t$ 的前缀，看是否与 $S$ 匹配。

---

第五步：高效算法

观察：对于固定 $n$，$R$ 的字符必须与 $S$ 中某些位置匹配。
我们可以通过回文约束推导出 $R$ 的字符。

考虑 $P_t$ 的结构：它总是关于中心对称的。
如果 $S$ 是 $P_t$ 的前缀，那么 $S$ 的某些位置必须相等（回文性质）。

我们可以枚举 $n$，对于每个 $n$，尝试用 $S$ 来填充 $R$ 的字符，检查是否存在一致的赋值。

---

具体做法（官方题解思路）：

定义过程 check(n)：

1. 令 $R$ 的字符为未知变量 $r_1, r_2, \dots, r_n$。
2. 我们知道 $S$ 是某个 $P_t$ 的前缀。
   初始 $P_0 = R$，如果 $|S| \le n$，则只需 $S$ 是 $R$ 的前缀，即 $r_i = S[i]$ 对 $i=1..|S|$。
   如果 $|S| > n$，则 $S$ 的前 $n$ 个字符必须等于 $R$。
3. 然后 $P_1$ 长度 $2n-1$，如果 $|S| > n$，那么 $S[n+1..\min(|S|, 2n-1)]$ 必须等于 $R[n-1..x]$ 的反转（回文对称部分）。
   这会给出对 $R$ 的更多约束。
4. 如果还有超出，继续考虑 $P_2$ 等，直到覆盖 $S$ 的长度。

在推导过程中，如果出现矛盾（同一个位置应同时等于两个不同字符），则 $n$ 不可行。

---

我们可以模拟这个推导过程，但不必显式生成整个串，而是用两个指针 $l, r$ 表示当前 $S$ 的匹配范围，并根据回文对称性添加约束。

---

第六步：实现方法

用并查集或直接数组记录每个位置的字符约束。
从 $R$ 的第一位开始，逐步根据 $S$ 的前缀匹配和回文对称性，推导 $R$ 的其他位置的字符。

如果推导完 $S$ 的所有字符后没有矛盾，则 $n$ 可行。

复杂度：对每个 $n$，推导过程 $O(|S|)$，总 $O(|S|^2)$ 太慢。
但注意到 $n$ 必须满足 $n$ 是某个可能的初始长度，实际上 $n$ 必须使得 $S$ 满足“可以从前缀扩展成某个 $P_t$”的性质。

---

第七步：更快速的判定法

已知 $S$ 是 $P_t$ 的前缀，那么 $S$ 本身必须是一个回文前缀链。

我们可以从 $S$ 的末尾开始，利用回文对称性往前推导 $R$。

具体做法（逆向推导）：

• 假设我们有了 $P_t$，它的最后一步翻转中心是某个字符。
• 这个中心字符在 $S$ 中对应位置是 $S[m]$（$m$ 是某个值）。
• 那么 $S$ 关于这个中心对称的部分必须相等。

我们可以枚举最后一次翻转的中心位置，然后向前回溯，看是否能回溯到某个长度 $n$。

---

第八步：最终算法（KMP + 回文）

实际上，本题标准解法是：

1. 预处理 $S$ 的每个前缀是否是回文（可以用 Manacher 或哈希）。
2. 定义 $next[i]$ 表示最大的 $j < i$ 使得 $S[1..j]$ 经过若干次翻转可以得到 $S[1..i]$ 的前缀（即 $S[1..j]$ 是某个 $P_t$ 且 $S[1..i]$ 是 $P_{t+1}$ 的前缀）。
3. 用类似 KMP 的方式递推 $next$ 数组。
4. 最终所有可能的 $n$ 就是 $next$ 链上的所有长度（包括 $|S|$ 本身）。

---

第九步：样例解释

样例 1：abcdcb

• 可能长度 4：abcd → abcdcba 前 6 字符是 abcdcb ✅
• 可能长度 6：abcdcb 本身（0 次翻转）✅
• 输出 4 6

样例 2：qwqwq

• 长度 2：qw → qwq → qwqwq ✅
• 长度 3：qwq → qwqwq ✅
• 长度 4：qwqw → qwqwqwq 前 5 字符是 qwqwq ✅
• 长度 5：本身 ✅
• 输出 2 3 4 5

---

第十步：总结

本题核心：

1. 翻转操作生成回文串。
2. $S$ 是某个生成回文串的前缀，对 $S$ 施加了回文约束。
3. 通过回文链递推（KMP-like）找出所有可能的初始长度 $n$。

复杂度 $O(|S|)$。

---