是什么、为什么、怎么用、以及经典应用。
什么是“环复回文”技巧？
我们来拆解这个概念：
-
环：指将一个线性结构（如字符串
s）的首尾相接，形成一个环状结构，想象一下，你把字符串s = "abc"的首尾连起来，就形成了一个圆环，a的后面是b，b的后面是c，而c的后面又回到了a。 -
复：指复制或拼接，为了在代码中模拟这个“环”，最简单直接的方法就是将原字符串复制一份，拼接到原字符串的后面。
s = "abc"变成s + s = "abcabc"。 -
回文：指正读反读都一样的字符串，如
"abba"或"abcba"。
核心思想：
将原字符串 s 复制一份拼接到自身后面，得到一个新字符串 t = s + s，在这个新字符串 t 中，任何长度为 n 的子串，都对应着原字符串 s 中的一种“环状”排列。
举个例子：
原字符串 s = "abcd"，长度为 4。
拼接后 t = "abcdabcd"。
我们来看 t 中长度为 4 的子串：
t[0:4] = "abcd"(原串)t[1:5] = "bcda"(相当于s向左旋转一位)t[2:6] = "cdab"(相当于s向左旋转两位)t[3:7] = "dabc"(相当于s向左旋转三位)
你看,通过在 t 中滑动一个长度为 n 的窗口，我们就可以遍历 s 所有可能的“环状”排列。
为什么这个技巧如此强大？
这个技巧的魔力在于它将一个复杂的“环状”或“循环”问题，转化成了一个简单的“线性”子串查找问题。
-
原问题：在
s的所有环状排列中，查找是否存在某个满足特定条件（如是回文）的子串，这很棘手，因为s的末尾和开头是相连的，处理边界条件很麻烦。 -
转化后的问题：在
t = s + s中，查找是否存在一个长度为n的子串满足特定条件，这是一个标准的字符串操作问题，有非常成熟的算法（如滑动窗口、KMP、Manacher算法等）可以解决，完全不需要考虑循环边界。
总结优势：
- 简化边界：消除了首尾相连的复杂性。
- 统一处理：将循环问题转化为线性问题，可以用现成的算法工具箱。
- 思路清晰：让问题的本质（查找特定模式的子串）更加凸显。
怎么用？（核心步骤）
使用这个技巧通常遵循以下三步：
步骤 1：拼接字符串
创建一个新字符串 t = s + s。
步骤 2：应用滑动窗口
在 t 上使用一个长度为 n（原字符串长度）的滑动窗口，窗口从 t[0] 开始，向右滑动，直到 t[n-1]。
步骤 3：在窗口内进行核心操作
对于窗口内的每一个子串 t[i:i+n]，执行你需要的核心逻辑，
- 判断是否为回文
- 查找某个特定模式
- 计算哈希值（用于高效比较）
经典应用场景
应用场景一：寻找最长的回文子串（LeetCode #5）
这是一个非常经典的例子,虽然最优解是 Manacher 算法，但“环复回文”的思路可以帮助我们更好地理解问题，并且可以用来解决一些变种。
问题：给定一个字符串 s，找到其中最长的回文子串。
“环复”思路的变种应用：
Manacher 算法在处理回文时，巧妙地处理了奇偶长度和边界问题，其核心思想之一，就是利用回文的对称性，并引入一个辅助数组 P 来记录以每个字符为中心的回文半径，这个过程虽然不直接拼接 s+s，但其“利用对称性避免重复计算”的思想与“环复”技巧有异曲同工之妙。
更直接的“环复”应用（寻找特定长度的回文）：
假设问题变成：“在字符串 s 的所有环状排列中，是否存在长度为 k 的回文子串？”
这时,“环复回文”技巧就派上用场了：
-
拼接：
t = s + s。 -
滑动窗口：在
t上使用一个长度为k的滑动窗口。 -
判断回文：对于窗口内的每一个子串
t[i:i+k]，使用双指针法判断它是否是回文。def is_palindrome(sub): left, right = 0, len(sub) - 1 while left < right: if sub[left] != sub[right]: return False left += 1 right -= 1 return True def find_circular_palindrome(s, k): n = len(s) if k > n: return False t = s + s for i in range(n): # 只需要遍历前 n 个窗口，因为后面的会重复 if is_palindrome(t[i:i+k]): return True return False
应用场景二：寻找重复的子串（LeetCode #459）
问题：给定一个非空的字符串 s，检查它是否可以通过由它的一个子串重复多次构成。
示例：
"abab"->True(由"ab"重复构成)"aba"->False"abcabcabc"->True(由"abc"重复构成)
“环复回文”思路的应用：
这个问题与“环”的概念高度相关，一个能被重复构成的字符串，其环状特性非常明显。
- 拼接：
t = s + s。 - 寻找子串：在
t中寻找一个等于s的子串，但这个子串不能是t的前半部分（即s本身）。 - 实现：
t = "abab" + "abab" = "abababab"- 我们想在
t中找到"abab"。 - 使用
find或index方法，从t的索引1开始查找（因为从0开始就是它自己）。 t.find(s, 1)会返回2，因为t[2:6]是"abab"，找到了，所以返回True。
为什么有效？
如果一个字符串 s 由长度为 k 的子串 p 重复 m 次构成 (s = p * m)，s + s 就等于 p * (2m)，在 s + s 中，从第二个 p 开始，必然能找到 s 这个模式，这个技巧巧妙地利用了重复字符串的周期性。
def repeatedSubstringPattern(s: str) -> bool:
# 处理边界情况
if not s:
return False
t = s + s
# 在 t 中查找 s，但跳过开头的那个 s
# s 是由子串重复构成的，那么必然能在中间找到它
# s="abab", t="abababab", t.find(s, 1) 会找到 "abab" (从索引2开始)
return t.find(s, 1) != -1
应用场景三：字符串旋转（LeetCode #796）
问题：给定两个字符串 s1 和 s2，编写代码判断 s2 是否是 s1 的旋转字符串。
示例：
s1 = "abcde",s2 = "cdeab"->True(将 "abcde" 向左旋转2位得到 "cdeab")s1 = "abcde",s2 = "abced"->False
“环复回文”思路的应用
