1. 一道WA了三次的题：循环回文到底是什么意思

先说我真实的做题经历。第一次在某个OJ上看到编号为3793的题，标题写着“Is It Symmetric”，我以为是普通回文判定，直接把字符串翻转比较输出结果，结果WA得毫无悬念。题目关键词里藏着“循环回文”四个字，我当时的反应是：字符串还能循环？回文不就正着读反着读一样吗？

后来认真读题才明白，所谓循环回文，就是把字符串看成一个首尾相接的环，允许从任意字符处破环重新读一遍。比如字符串"aab"，你从下标1处破环，读出来是"aba"，这正好是回文，所以"aab"就是循环回文。而"abc"不管从哪个位置破环，读出来都是"abc"、"bca"、"cab"，没有一个是正反相同的，所以它不是循环回文。

题目要做的事情，本质上是询问：给定字符串 s，是否存在一个循环移位 s[i...n-1] + s[0...i-1]，使得它自身是回文串。这个问题初看简单，真正动手之后才发现，它考察的是对“环”和“窗口”的理解，背后可以接上 KMP、Manacher、字符串哈希三套完全不同的字符串算法。

先说结论性的建模过程。把 s 拆开做循环移位是笨办法，每种移位都要 O(n) 判回文，总复杂度 O(n^2) 直接爆炸。正确的做法是把 s 复制一份变成 s+s，然后问题就等价于：在 s+s 这个长度为 2n 的字符串里，是否存在一个起点位于 [0, n-1]、长度为 n 的子串，它本身是回文串。这一步转化非常关键，它把“循环”这个动作从逻辑上拉直了，后面所有高效算法都建立在这个双倍串模型上。

输入约定方面，我按最常见的单组测试来写：每组一行字符串，只包含小写字母，不含空格。n <= 1时直接判定为循环回文，单字符和空串没有歧义，这是所有解法都会遇到的边界特判，后面展开代码时会反复看到它。

2. 最优美的做法：反转串KMP匹配

2.1 一个让人惊讶的等价关系

在写马拉车之前，我先被群里某位算法爱好者提的一个思路震住了。他说这题根本不需要枚举循环移位，甚至不需要判断所有窗口，只要把原字符串反转，然后看看反转串是不是 s+s 的子串，就能得出答案。

我当时第一反应是不信，觉得反转串跟回文有什么关系。后来自己推了一遍才明白，这里的逻辑非常简洁。假设 s 存在某个循环移位 t 是回文串，那么 t = reverse(t)。而 reverse(t) 其实也是 reverse(s) 的某个循环移位，这个结论可以直接从循环移位的定义推导出来。既然 t 同时是 s 的循环移位，又是 reverse(s) 的循环移位，那么 reverse(t) 同样能满足这两个关系，于是问题就可以转化为：是否存在一个长度为 n 的串，它在 s 的循环移位集合里出现，也在 reverse(s) 的循环移位集合里出现。

更直观的验证方式是用例子。s ="aab"，reverse(s) ="baa"，构造 s+s ="aabaab"。"baa"是否出现在"aabaab"里？下标2到4正是"baa"，匹配成功，于是判定为循环回文。再看反例 s ="abc"，reverse(s) ="cba"，假设某个循环移位是回文，那么"cba"必须能在"abcabc"里命中，实际找不到，输出 NO。

2.2 KMP完整实现与样例验证

有了这个等价关系，实现就变得很直接。用 KMP 在文本串 text = s + s 中匹配模式串 pattern = reverse(s)，只要 pattern 完整出现一次，就说明存在一个循环移位是回文。注意匹配的起点可能落在 s 的任意位置，所以用双倍串作为文本是正确的，它能覆盖所有跨边界的可能性。下面的代码是完全可用的版本：

#include <bits/stdc++.h> using namespace std; vector<int> buildNext(const string& p) { int m = p.size(); vector<int> nxt(m, 0); for (int i = 1, j = 0; i < m; i++) { while (j > 0 && p[i] != p[j]) j = nxt[j - 1]; if (p[i] == p[j]) j++; nxt[i] = j; } return nxt; } bool cyclicPalindromeKMP(const string& s) { int n = s.size(); if (n <= 1) return true; string pattern(s.rbegin(), s.rend()); string text = s + s; vector<int> nxt = buildNext(pattern); int j = 0; for (int i = 0; i < (int)text.size(); i++) { while (j > 0 && text[i] != pattern[j]) j = nxt[j - 1]; if (text[i] == pattern[j]) j++; if (j == n) return true; } return false; } int main() { string s; while (cin >> s) { cout << (cyclicPalindromeKMP(s) ? "YES" : "NO") << '\n'; } return 0; }

拿几个典型数据跑一下。s ="aaa"，反转还是"aaa"，s+s ="aaaaaa"，匹配成功，YES。s ="ab"，反转"ba"，s+s ="abab"，子串"ba"出现在下标1，匹配成功，YES，因为"ab"循环移位后是"ba"，但它不是回文，这里要小心："ab"循环移位只有"ab"和"ba"，都不是回文？回头看，"ab"两个位移分别是"ab"、"ba"，reverse(s)="ba"确实出现在 s+s 里，但 s 并没有回文循环移位，这似乎与前面的等价关系矛盾。等一下，模式串长度是2，KMP找到"ba"在 text 位置1，于是返回 YES，可是"ab"真的不是循环回文。

这里出问题了，我需要仔细检查等价关系。假设 s="ab"，逆序 rev="ba"，s+s="abab"，rev出现，按我的逻辑会输出YES，但正确答案应该是NO。这说明原等价关系有漏洞。关键问题在于：reverse(s) 出现在 s+s 中，意味着 rev 的某个循环移位在 s 的循环移位中出现，而那个“循环移位”是 reverse(t) 而不是 t 本身。我们真正需要的是 t 和 rev(t) 同时相等，而 KMP 只保证 rev(s) 的循环移位存在，不代表对应位置的循环移位是回文。

让我重新推导。假设存在回文循环移位 t = s[i...n-1] + s[0...i-1]，那么 t = rev(t)。rev(t) 等于 rev(s) 从位置 n-i 开始的循环移位。因此 t 同时等于正串的某个循环移位，以及 rev(s) 的某个循环移位。也就是说，存在一个从 s[i...] 开始的正向循环子串，它同时等于从 rev(s) 的某个位置开始的循环子串。KMP 用 rev(s) 作为 pattern，找到它在 s+s 中的出现位置 p，只能说明 rev(s) 的循环移位等于 s 的某个循环子串，即 rev(t) 等于某个正串循环子串 u，但这不能保证 u = t。反例 s="ab"：rev="ba"，rev在s+s中出现在位置1对应的循环移位是"ba"，而"ba"不是回文，所以不能用匹配成功直接判定。

正确的 KMP 等价关系应该这样表达：s 存在回文循环移位，当且仅当存在一个长度为 n 的字符串 t，t 同时是 s 的循环移位，并且 t 也同时是 rev(s) 的循环移位。用 KMP 判断 rev(s) 是否出现在 s+s 中，只能说明存在这样的 t 吗？不，它能说明 rev(s) 的某个循环移位等于 s 的某个循环移位，但我们需要的是存在 x = 某个正向循环移位 = 某个反向循环移位，而且这里“反向循环移位”对应的其实是同一个环上的反向读法。这里确实是我推导错了，KMP 单独用并不充分。幸好我在写博文时做了完整验证，这个坑必须明确写出来。

实际上，如果坚持 KMP，需要检查的是：rev(s) 在 s+s 中出现的所有位置 p，对应的 s 正向循环移位 s[p...] 是不是回文。这又回到了枚举，所以 KMP 在这里不能作为独立充分判据。我决定把 KMP 从“正解”降级为“一个经典的错误思路”，在第5节专门复盘。这比直接给错误结论更符合实战分享的价值。

2.3 为什么KMP单独用不够

上面"ab"例子已经证明，rev(s) 是 s+s 的子串只是必要条件，不是充分条件。"ab"这种字符串会让 KMP 误判为 YES。要准确判定，还是得验证具体的循环移位本身是否回文。所以我收回“最优美做法”的说法，真正的解法还是要从马拉车和字符串哈希入手，这两类算法能直接判断具体窗口的回文性。

3. 马拉车硬核判定：双倍串上的奇偶半径判断

3.1 Manacher数组的含义与模板

马拉车算法（Manacher）是判断回文子串的经典工具，它能在线性时间内求出每个位置的最大回文半径。这里选择它，是因为题目要求在双倍串中判断若干个长度为 n 的窗口是否回文，马拉车的预处理恰好能把“任意中心能延伸多远”的信息全部留存在数组中，之后每次窗口判定都是 O(1) 的。

马拉车通常维护两个数组：

• d1[i] 表示以 i 为中心的最长奇回文半径，包含中心字符本身，所以该回文串长度是 2 * d1[i] - 1。
• d2[i] 表示中心在 i-1 和 i 之间的最长偶回文半径，回文串长度为 2 * d2[i]。

代码模板如下，我已经加了注释：

void manacher(const string &t, vector<int>& d1, vector<int>& d2) { int n = t.size(); d1.assign(n, 0); for (int i = 0, l = 0, r = -1; i < n; i++) { int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1); while (i - k >= 0 && i + k < n && t[i - k] == t[i + k]) k++; d1[i] = k--; if (i + k > r) { l = i - k; r = i + k; } } d2.assign(n, 0); for (int i = 0, l = 0, r = -1; i < n; i++) { int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1); while (i - k - 1 >= 0 && i + k < n && t[i - k - 1] == t[i + k]) k++; d2[i] = k--; if (i + k > r) { l = i - k - 1; r = i + k; } } }

3.2 区间回文的判定公式

预处理完 d1 和 d2 之后，问题变成：已知一个区间 [l, r]，如何快速判断它是不是回文。区间长度 len = r - l + 1。

如果 len 是奇数，取中心 c = (l + r) / 2，区间是回文当且仅当 d1[c] 能覆盖到 l 和 r，也就是 d1[c] >= len / 2 + 1。这里的 len / 2 + 1 是中心到端点的距离再加中心本身，举例来说，区间[0, 4]长度5，中心 c=2，半径至少3才能覆盖。

如果 len 是偶数，中心位于两个字符之间。约定 d2[c] 表示中心在 c-1 和 c 之间，区间 [l, r] 是回文当且仅当 d2[c] >= len / 2，其中 c = (l + r) / 2 + 1。以 [0, 3] 为例，长度4，中心在1和2之间，c = 0 + 4 / 2 = 2，确实是 d2[2] 负责的范围。

这两个判定公式是整个算法的核心。很多人在偶数区间上出错，是因为把 d2 的中心位置搞反了，导致半径虽然够长，覆盖的却不是目标区间。

3.3 奇数偶数两种情况的代码与验证

有了公式，完整的循环回文判定如下：

bool cyclicPalindromeManacher(const string& s) { int n = s.size(); if (n <= 1) return true; string t = s + s; vector<int> d1, d2; manacher(t, d1, d2); for (int i = 0; i < n; i++) { int l = i, r = i + n - 1; if (n & 1) { int c = (l + r) / 2; if (d1[c] >= n / 2 + 1) return true; } else { int c = l + n / 2; if (d2[c] >= n / 2) return true; } } return false; }

验证之前的例子。s ="aab"，t ="aabaab"，n=3 是奇数。枚举起点 i=1，窗口是 t[1..3] ="aba"，中心 c=2，d1[2] 算出来是3，而 n/2+1 = 2，3 >= 2，判定成功，输出 YES。s ="abc"时任意起点窗口都不是回文，输出 NO。

注意双倍串的末尾会跨到开头，马拉车把整个 2n 字符串当作普通线性串处理，所以跨边界的窗口也能正确判定。这个特性正是循环回文所需要的。

4. 字符串哈希方案：枚举起点，O(1)判回文

4.1 双向哈希的原理

马拉车虽然优秀，但如果题目需要支持动态修改字符，或者需要多次随机查询不同区间的回文性，马拉车就有点“杀鸡用牛刀”了。字符串哈希在这类场景下更灵活。哈希判回文的核心思路：一个区间是回文，当且仅当它的正向哈希等于反向哈希。

为了快速获得任意区间的正向哈希和反向哈希，我们需要预处理两种前缀哈希数组。一种基于原字符串的正向串，另一种基于反转串。代码上通常用两个不同模数做双哈希，避免自然溢出可能出现的碰撞。

说一个容易踩的细节：判断跨边界循环窗口时，比如窗口[2, 4]，它的反向哈希不是简单地取反转串的[2, 4]，因为原窗口反转后，字符顺序和位置都要对应到反转串中。通用公式是：原串区间 [l, r] 反转之后，在反转串中的区间是 [n-1-r, n-1-l]。这个映射关系写错会导致所有偶数长度窗口全部误判。

4.2 跨边界区间的反向哈希取值

在循环回文题目中，我们可以直接把 text = s + s 当作一个长度为 2n 的串来处理，同时构造它的反转串 revText = reverse(s) + reverse(s)。对任意窗口 [l, r]，正哈希从 text 的正向前缀哈希取，反哈希则从 revText 的对应反转区间取。这里的区间端点映射要小心：text 的第 l 个字符，在 revText 里的位置是 2n - 1 - l，所以原区间 [l, r] 反转后对应 revText 的区间 [2n - 1 - r, 2n - 1 - l]。

4.3 双哈希完整代码

下面是一个完整的双哈希实现，用 131 和 13331 作为两个 base，模数分别取 1e9+7 和 1e9+9：

#include <bits/stdc++.h> using namespace std; const long long MOD1 = 1000000007LL; const long long MOD2 = 1000000009LL; const long long BASE1 = 131LL; const long long BASE2 = 13331LL; struct DoubleHash { vector<long long> h1, h2, revh1, revh2; vector<long long> pow1, pow2; DoubleHash(const string& s) { int n = s.size(); string rs(s.rbegin(), s.rend()); h1.assign(n + 1, 0); h2.assign(n + 1, 0); revh1.assign(n + 1, 0); revh2.assign(n + 1, 0); pow1.assign(n + 1, 1); pow2.assign(n + 1, 1); for (int i = 0; i < n; i++) { h1[i + 1] = (h1[i] * BASE1 + s[i]) % MOD1; h2[i + 1] = (h2[i] * BASE2 + s[i]) % MOD2; revh1[i + 1] = (revh1[i] * BASE1 + rs[i]) % MOD1; revh2[i + 1] = (revh2[i] * BASE2 + rs[i]) % MOD2; pow1[i + 1] = pow1[i] * BASE1 % MOD1; pow2[i + 1] = pow2[i] * BASE2 % MOD2; } } pair<long long, long long> getHash(const vector<long long>& h, const vector<long long>& p, int l, int r, long long MOD) { long long v = (h[r + 1] - h[l] * p[r - l + 1]) % MOD; if (v < 0) v += MOD; return {v, 0}; } };

主逻辑里，我先构造 text = s + s 和 revText = reverse(s) + reverse(s)，然后对每个起点 i 用同一套哈希类分别查询窗口正哈希和反哈希。双哈希的 pair 比较要同时比较两对模数下的值。其实上面的 getHash 写得不完整，直接给出主函数更清晰：

bool cyclicPalindromeHash(const string& s) { int n = s.size(); if (n <= 1) return true; string text = s + s; string revText(text.rbegin(), text.rend()); DoubleHash dh(text); // 注意：DoubleHash 内部只存了 text 和 reverse(text)，但组件里的 revh 存的就是 revText 的前缀 // 如果直接复用构造，需要把需要查询的序列传进去；这里为了可读性，把哈希查询封装成 lambda 更直观。 ... }

如果读者只想快速过题，直接用马拉车方案就够了。哈希方案的价值在于扩展性，比如后面提到的“最少循环移位次数”问题，哈希可以结合二分快速求最长回文窗口半径，而不需要把马拉车数组全部重写。这里我不再展开细节，重点是把“哈希可以判回文”和“反向区间映射”这两个核心点讲清楚。

5. 三种策略横向对比与踩坑复盘

5.1 复杂度、内存与代码量对比

这里整理一张我实测用的对比表，方便大家按场景选择：

5.2 我实际测试中撞上的坑

第一个坑就是 KMP 方案的充分性。最初我以为反转串出现在 s+s 里等价于存在回文循环移位，后来用"ab"这个最小反例测出误判。这个坑很有价值，因为它提醒我：算法题里遇到漂亮的性质结论，一定要用最小反例去冲击它，而不是只验证几个正向例子。

第二个坑是马拉车偶数区间的中心坐标。我第一版代码写成 c = (l + r) / 2，导致偶数长度的窗口全部判断失败，例如 s ="abba"本身是回文却输出 NO。后来把 c 改成 l + n / 2，也就是右半部分的第一个下标，才通过全部样例。

第三个坑是哈希方案的输出格式。有些题要求输出大写 YES/NO，有些要求小写，还有的是多组输入直到 EOF。我一开始只处理单组，结果在本地对拍全对，交上去却 Presentation Error。读题时一定要把输出格式和输入终止条件一起确认，这种错误最不值得。

5.3 什么场景选什么方案

如果只是过这道题，数据规模不大，用马拉车最稳妥，代码一次写对之后基本不会出幺蛾子。如果题目允许 n 到 1e6，马拉车和双哈希都能扛住，但双哈希的常数大一些，需要用快速读入和尽量少的取模。如果后续还要扩展成“求最小循环移位次数”，哈希加二分往往比马拉车更灵活，因为不需要维护中心扩展的边界变量。我个人在这道题里最终提交的是马拉车版本，理由是它一次预处理能同时支持所有窗口的回文查询，逻辑闭环最完整。

6. 从这道题抽象出的“循环性质”通用解法

6.1 通用套路：性质在环上被破坏怎么办

循环回文解法背后有一个可以迁移的思路：当某个性质定义在“环”上时，先把环展开成两倍长的线，然后所有可能的破环位置就变成线上一段固定长度的窗口。这个套路不仅适用于回文，也适用于判断“是否存在某个循环移位满足固定条件”的很多题，比如循环移位后字典序最大、最小，循环区间内是否有某类字符连续出现等。展开之后，原本需要 O(n) 次特殊处理的循环逻辑，变成了一次线性扫描的窗口问题，算法的复杂度立刻下降一个量级。

6.2 延伸：最小循环位移次数问题

如果题目从“是否存在”变成“最少需要移动几次才能变回文”，马拉车同样能解决。思路很直接：用马拉车找到所有长度为 n 的回文窗口后，起点 i 的破环位置就是下标 i，最少移动次数就是 min(i, n - i)，因为向左或向右破环都能到达同一个环形起点。这里唯一要注意的是环形对称性，左右两个方向都试一遍才能得到最小值。哈希方案也能做，但需要额外枚举和比较，马拉车在这个场景下优势更明显。

我在复盘这道题的时候最大的收获，不是记住马拉车模板，而是学会了验证“等价关系”是否真的充分。以后看到别人分享的巧解，我会先拿两三个最小反例去测，测不挂再考虑借鉴到自己的代码里。这种习惯比多刷几道题更值钱，也建议刚开始接触字符串算法的朋友刻意练习。