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 复制一份变成 ss然后问题就等价于在 ss 这个长度为 2n 的字符串里是否存在一个起点位于 [0, n-1]、长度为 n 的子串它本身是回文串。这一步转化非常关键它把“循环”这个动作从逻辑上拉直了后面所有高效算法都建立在这个双倍串模型上。输入约定方面我按最常见的单组测试来写每组一行字符串只包含小写字母不含空格。n 1时直接判定为循环回文单字符和空串没有歧义这是所有解法都会遇到的边界特判后面展开代码时会反复看到它。2. 最优美的做法反转串KMP匹配2.1 一个让人惊讶的等价关系在写马拉车之前我先被群里某位算法爱好者提的一个思路震住了。他说这题根本不需要枚举循环移位甚至不需要判断所有窗口只要把原字符串反转然后看看反转串是不是 ss 的子串就能得出答案。我当时第一反应是不信觉得反转串跟回文有什么关系。后来自己推了一遍才明白这里的逻辑非常简洁。假设 s 存在某个循环移位 t 是回文串那么 t reverse(t)。而 reverse(t) 其实也是 reverse(s) 的某个循环移位这个结论可以直接从循环移位的定义推导出来。既然 t 同时是 s 的循环移位又是 reverse(s) 的循环移位那么 reverse(t) 同样能满足这两个关系于是问题就可以转化为是否存在一个长度为 n 的串它在 s 的循环移位集合里出现也在 reverse(s) 的循环移位集合里出现。更直观的验证方式是用例子。s aabreverse(s) baa构造 ss aabaab。baa是否出现在aabaab里下标2到4正是baa匹配成功于是判定为循环回文。再看反例 s abcreverse(s) cba假设某个循环移位是回文那么cba必须能在abcabc里命中实际找不到输出 NO。2.2 KMP完整实现与样例验证有了这个等价关系实现就变得很直接。用 KMP 在文本串 text s s 中匹配模式串 pattern reverse(s)只要 pattern 完整出现一次就说明存在一个循环移位是回文。注意匹配的起点可能落在 s 的任意位置所以用双倍串作为文本是正确的它能覆盖所有跨边界的可能性。下面的代码是完全可用的版本#include bits/stdc.h using namespace std; vectorint buildNext(const string p) { int m p.size(); vectorint 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; vectorint 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反转还是aaass aaaaaa匹配成功YES。s ab反转bass abab子串ba出现在下标1匹配成功YES因为ab循环移位后是ba但它不是回文这里要小心ab循环移位只有ab和ba都不是回文回头看ab两个位移分别是ab、bareverse(s)ba确实出现在 ss 里但 s 并没有回文循环移位这似乎与前面的等价关系矛盾。等一下模式串长度是2KMP找到ba在 text 位置1于是返回 YES可是ab真的不是循环回文。这里出问题了我需要仔细检查等价关系。假设 sab逆序 revbassababrev出现按我的逻辑会输出YES但正确答案应该是NO。这说明原等价关系有漏洞。关键问题在于reverse(s) 出现在 ss 中意味着 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找到它在 ss 中的出现位置 p只能说明 rev(s) 的循环移位等于 s 的某个循环子串即 rev(t) 等于某个正串循环子串 u但这不能保证 u t。反例 sabrevbarev在ss中出现在位置1对应的循环移位是ba而ba不是回文所以不能用匹配成功直接判定。正确的 KMP 等价关系应该这样表达s 存在回文循环移位当且仅当存在一个长度为 n 的字符串 tt 同时是 s 的循环移位并且 t 也同时是 rev(s) 的循环移位。用 KMP 判断 rev(s) 是否出现在 ss 中只能说明存在这样的 t 吗不它能说明 rev(s) 的某个循环移位等于 s 的某个循环移位但我们需要的是存在 x 某个正向循环移位 某个反向循环移位而且这里“反向循环移位”对应的其实是同一个环上的反向读法。这里确实是我推导错了KMP 单独用并不充分。幸好我在写博文时做了完整验证这个坑必须明确写出来。实际上如果坚持 KMP需要检查的是rev(s) 在 ss 中出现的所有位置 p对应的 s 正向循环移位 s[p...] 是不是回文。这又回到了枚举所以 KMP 在这里不能作为独立充分判据。我决定把 KMP 从“正解”降级为“一个经典的错误思路”在第5节专门复盘。这比直接给错误结论更符合实战分享的价值。2.3 为什么KMP单独用不够上面ab例子已经证明rev(s) 是 ss 的子串只是必要条件不是充分条件。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, vectorint d1, vectorint 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中心 c2半径至少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; vectorint 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 aabt aabaabn3 是奇数。枚举起点 i1窗口是 t[1..3] aba中心 c2d1[2] 算出来是3而 n/21 23 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模数分别取 1e97 和 1e99#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 { vectorlong long h1, h2, revh1, revh2; vectorlong 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; } } pairlong long, long long getHash(const vectorlong long h, const vectorlong 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 复杂度、内存与代码量对比这里整理一张我实测用的对比表方便大家按场景选择方案预处理复杂度单组判断复杂度额外空间代码量主要风险朴素枚举中心扩展O(1)O(n^2)O(1)最短数据大于1e4必超时马拉车O(n)O(n)O(n)中等偶数区间公式易写错双哈希枚举O(n)O(n)O(n)较长边界映射和碰撞处理“反转串KMP”思路O(n)O(n)O(n)最短不充分会误判5.2 我实际测试中撞上的坑第一个坑就是 KMP 方案的充分性。最初我以为反转串出现在 ss 里等价于存在回文循环移位后来用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)因为向左或向右破环都能到达同一个环形起点。这里唯一要注意的是环形对称性左右两个方向都试一遍才能得到最小值。哈希方案也能做但需要额外枚举和比较马拉车在这个场景下优势更明显。我在复盘这道题的时候最大的收获不是记住马拉车模板而是学会了验证“等价关系”是否真的充分。以后看到别人分享的巧解我会先拿两三个最小反例去测测不挂再考虑借鉴到自己的代码里。这种习惯比多刷几道题更值钱也建议刚开始接触字符串算法的朋友刻意练习。
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 复制一份变成 ss然后问题就等价于在 ss 这个长度为 2n 的字符串里是否存在一个起点位于 [0, n-1]、长度为 n 的子串它本身是回文串。这一步转化非常关键它把“循环”这个动作从逻辑上拉直了后面所有高效算法都建立在这个双倍串模型上。输入约定方面我按最常见的单组测试来写每组一行字符串只包含小写字母不含空格。n 1时直接判定为循环回文单字符和空串没有歧义这是所有解法都会遇到的边界特判后面展开代码时会反复看到它。2. 最优美的做法反转串KMP匹配2.1 一个让人惊讶的等价关系在写马拉车之前我先被群里某位算法爱好者提的一个思路震住了。他说这题根本不需要枚举循环移位甚至不需要判断所有窗口只要把原字符串反转然后看看反转串是不是 ss 的子串就能得出答案。我当时第一反应是不信觉得反转串跟回文有什么关系。后来自己推了一遍才明白这里的逻辑非常简洁。假设 s 存在某个循环移位 t 是回文串那么 t reverse(t)。而 reverse(t) 其实也是 reverse(s) 的某个循环移位这个结论可以直接从循环移位的定义推导出来。既然 t 同时是 s 的循环移位又是 reverse(s) 的循环移位那么 reverse(t) 同样能满足这两个关系于是问题就可以转化为是否存在一个长度为 n 的串它在 s 的循环移位集合里出现也在 reverse(s) 的循环移位集合里出现。更直观的验证方式是用例子。s aabreverse(s) baa构造 ss aabaab。baa是否出现在aabaab里下标2到4正是baa匹配成功于是判定为循环回文。再看反例 s abcreverse(s) cba假设某个循环移位是回文那么cba必须能在abcabc里命中实际找不到输出 NO。2.2 KMP完整实现与样例验证有了这个等价关系实现就变得很直接。用 KMP 在文本串 text s s 中匹配模式串 pattern reverse(s)只要 pattern 完整出现一次就说明存在一个循环移位是回文。注意匹配的起点可能落在 s 的任意位置所以用双倍串作为文本是正确的它能覆盖所有跨边界的可能性。下面的代码是完全可用的版本#include bits/stdc.h using namespace std; vectorint buildNext(const string p) { int m p.size(); vectorint 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; vectorint 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反转还是aaass aaaaaa匹配成功YES。s ab反转bass abab子串ba出现在下标1匹配成功YES因为ab循环移位后是ba但它不是回文这里要小心ab循环移位只有ab和ba都不是回文回头看ab两个位移分别是ab、bareverse(s)ba确实出现在 ss 里但 s 并没有回文循环移位这似乎与前面的等价关系矛盾。等一下模式串长度是2KMP找到ba在 text 位置1于是返回 YES可是ab真的不是循环回文。这里出问题了我需要仔细检查等价关系。假设 sab逆序 revbassababrev出现按我的逻辑会输出YES但正确答案应该是NO。这说明原等价关系有漏洞。关键问题在于reverse(s) 出现在 ss 中意味着 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找到它在 ss 中的出现位置 p只能说明 rev(s) 的循环移位等于 s 的某个循环子串即 rev(t) 等于某个正串循环子串 u但这不能保证 u t。反例 sabrevbarev在ss中出现在位置1对应的循环移位是ba而ba不是回文所以不能用匹配成功直接判定。正确的 KMP 等价关系应该这样表达s 存在回文循环移位当且仅当存在一个长度为 n 的字符串 tt 同时是 s 的循环移位并且 t 也同时是 rev(s) 的循环移位。用 KMP 判断 rev(s) 是否出现在 ss 中只能说明存在这样的 t 吗不它能说明 rev(s) 的某个循环移位等于 s 的某个循环移位但我们需要的是存在 x 某个正向循环移位 某个反向循环移位而且这里“反向循环移位”对应的其实是同一个环上的反向读法。这里确实是我推导错了KMP 单独用并不充分。幸好我在写博文时做了完整验证这个坑必须明确写出来。实际上如果坚持 KMP需要检查的是rev(s) 在 ss 中出现的所有位置 p对应的 s 正向循环移位 s[p...] 是不是回文。这又回到了枚举所以 KMP 在这里不能作为独立充分判据。我决定把 KMP 从“正解”降级为“一个经典的错误思路”在第5节专门复盘。这比直接给错误结论更符合实战分享的价值。2.3 为什么KMP单独用不够上面ab例子已经证明rev(s) 是 ss 的子串只是必要条件不是充分条件。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, vectorint d1, vectorint 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中心 c2半径至少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; vectorint 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 aabt aabaabn3 是奇数。枚举起点 i1窗口是 t[1..3] aba中心 c2d1[2] 算出来是3而 n/21 23 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模数分别取 1e97 和 1e99#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 { vectorlong long h1, h2, revh1, revh2; vectorlong 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; } } pairlong long, long long getHash(const vectorlong long h, const vectorlong 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 复杂度、内存与代码量对比这里整理一张我实测用的对比表方便大家按场景选择方案预处理复杂度单组判断复杂度额外空间代码量主要风险朴素枚举中心扩展O(1)O(n^2)O(1)最短数据大于1e4必超时马拉车O(n)O(n)O(n)中等偶数区间公式易写错双哈希枚举O(n)O(n)O(n)较长边界映射和碰撞处理“反转串KMP”思路O(n)O(n)O(n)最短不充分会误判5.2 我实际测试中撞上的坑第一个坑就是 KMP 方案的充分性。最初我以为反转串出现在 ss 里等价于存在回文循环移位后来用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)因为向左或向右破环都能到达同一个环形起点。这里唯一要注意的是环形对称性左右两个方向都试一遍才能得到最小值。哈希方案也能做但需要额外枚举和比较马拉车在这个场景下优势更明显。我在复盘这道题的时候最大的收获不是记住马拉车模板而是学会了验证“等价关系”是否真的充分。以后看到别人分享的巧解我会先拿两三个最小反例去测测不挂再考虑借鉴到自己的代码里。这种习惯比多刷几道题更值钱也建议刚开始接触字符串算法的朋友刻意练习。
