入门：回文、最长回文子串与 Z 函数
基于通用算法概念 · 核于 2026-07
速查
- 回文定义：串
s的子串s[l..r]是回文，当且仅当它正读反读相同（s[i] === s[r-(i-l)]对所有i成立）——单字符、空串都是回文；回文分奇长度（中心一个字符，如aba）和偶长度（中心两字符间，如abba）两类。 - 最长回文子串问题：给定
s，求其最长的回文子串——朴素 O(n³)（枚举所有子串 + 判回文），优化到 O(n²) 的中心扩展法（枚举每个中心向两侧扩展），Manacher 进一步压到 O(n)。 - 中心扩展法 O(n²)：以每个位置（及每两个位置之间）为中心，向两侧逐字符比较直到不对称——共
2n-1个中心，每个最多扩展 O(n)，总 O(n²)；它朴素就朴素在「每个中心都从 0 开始重新扩展，不借用已算结果」。 - Manacher 引入：核心观察是「回文有对称性」——若已算出某个大回文
[L,R]（中心c），那么它内部、关于c对称的位置i的回文半径，可以从镜像位置j = 2c - i的已知半径借用初值，不必从 0 扩展。 - Manacher 预处理（分隔符）：在字符之间插入
#（如aba→#a#b#a#），让奇偶长度统一——预处理后所有回文都以「某个字符」为中心且半径表示统一，#作中心对应原串偶长度回文，字符作中心对应奇长度回文。 - p 数组（回文半径）：
p[i]= 预处理后以i为中心的最长回文半径（含中心）——还原回原串长度：p[i] - 1就是原串中以对应位置为中心的最长回文子串长度。 - Manacher 复杂度 O(n)：维护「已触及的最右回文右端
r」及其中心c，r在整个过程中单调右移、总推进 ≤ n，扩展字符比较总次数 ≤ 2n——这就是线性的证明。 - Z 函数定义：对串
s，z[i]=s与s[i:]（即从i开始的后缀）的最长公共前缀长度；通常约定z[0] = 0（或n，因实现而异，本站按 0 约定以避免特判），z[1..]才是有意义的部分。 - Z 函数示例：
s = "ababa"，则z = [0, 0, 3, 0, 1]（s[2:]="aba"与s="ababa"最长公共前缀是"aba"长度 3）。 - Z-box 加速 O(n)：维护当前触及最右的匹配段
[l, r]（满足s[l..r] === s[0..r-l]），对当前i，若i < r则从min(z[i-l], r-i)起步扩展，否则从 0 起步——r同样单调右移，总比较 ≤ 2n，O(n) 构造。 - Z 函数应用：①字符串匹配（模式
pat+ 分隔符 + 主串txt拼成一串求 Z，z[i] == |pat|处即匹配点）；②最小周期（最小的p使z[p] == n-p，即串是长度p的循环节重复）；③判重复子串 / 后缀与整体关系。 - 两者共性：Manacher 与 Z 函数都是「复用已算信息 + 维护一个单调右移的最右边界来摊还」的线性字符串算法——理解了「单调右端点」的摊还，就理解了为什么两者都是 O(n)。
一、回文：定义与奇偶
回文（Palindrome）指正读反读都一样的字符串。形式化地，子串 s[l..r] 是回文当且仅当：
对所有 l ≤ i ≤ r：s[i] === s[l + r - i]即关于中心对称的每对字符都相等。注意回文有两种长度形态：
- 奇长度回文：中心是「一个字符」。如
aba、abcba，中心分别是b、c。 - 偶长度回文：中心是「两个相邻字符之间」。如
abba、abccba，中心分别在两个b、两个c之间。
这「奇偶两类」在朴素算法里要分别处理，是 Manacher「插入分隔符」技巧要解决的核心麻烦（见下一节）。
二、最长回文子串：朴素中心扩展 O(n²)
最长回文子串（Longest Palindromic Substring）是回文算法的经典问题：给定串 s，求其最长的回文子串。最直观的优化做法是中心扩展法：
- 共有
2n - 1个「中心」（n个字符中心 +n - 1个字符间隙中心）。 - 对每个中心，从中心向两侧逐字符比较，直到两侧字符不等或越界——记录最长。
// 朴素中心扩展法：O(n²)
function longestPalindrome(s) {
function expand(l, r) { // 以 [l,r] 为中心（l==r 奇，l+1==r 偶）向两侧扩展
while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; }
return [l + 1, r - 1]; // 返回最长回文的左右闭下标
}
let best = [0, 0];
for (let c = 0; c < s.length; c++) {
let [l1, r1] = expand(c, c); // 奇长度中心
let [l2, r2] = expand(c, c + 1); // 偶长度中心
if (r1 - l1 > best[1] - best[0]) best = [l1, r1];
if (r2 - l2 > best[1] - best[0]) best = [l2, r2];
}
return s.slice(best[0], best[1] + 1);
}复杂度 O(n²)：2n - 1 个中心，每个最坏扩展 O(n)。它朴素在哪？——每个中心都从「半径 0」开始重新向两侧比较，完全不借用附近已算出的回文信息。这就是 Manacher 要打破的瓶颈。
三、Manacher：从 O(n²) 到 O(n)
Manacher 的核心洞察是「回文具有对称性，已算的大回文内部的位置可以镜像借用」。设想你已经算出以 c 为中心、覆盖 [L, R] 的一个大回文；现在要算 c 右侧某点 i（i < R）的回文半径。由于 [L, R] 整体关于 c 对称，i 的镜像点 j = 2c - i（在 c 左侧）的回文半径已经算过了——i 的回文半径至少与 j 的（在不超过 R 的范围内）相同，所以不必从 0 扩展，直接以 min(p[j], R - i) 为初值起步即可。
为了让「奇偶两类中心」统一处理，Manacher 先做预处理：在原串每两个字符之间（含首尾）插入一个不在字符集里的分隔符 #。例如 aba → ^#a#b#a#$（两端哨兵可选）。预处理后：
- 所有回文都以「某个字符位置」为中心，且长度恒为奇数（因
#把字符隔开，对称结构天然以一个位置为中心）。 #作中心 ↔ 原串的偶长度回文；原字符作中心 ↔ 原串的奇长度回文。- 原串最长回文子串长度 =
max(p) - 1（预处理后回文半径p[i]与原串长度的换算关系）。
加上「最右回文右端 R 单调右移、总推进 ≤ n」的摊还分析，Manacher 整体 O(n)。完整推导与代码见Manacher 算法。
四、Z 函数：另一个线性算法
Z 函数（Z-function，又称 扩展 KMP）是另一条独立的线性字符串算法线。它定义在「串与其后缀的公共前缀」上：
z[i] = s 与 s[i:] 的最长公共前缀长度（即 s[0..] 与 s[i..] 最多有多少个字符相同）约定 z[0] = 0（避免与「整串与自身」的平凡情形混淆；也有约定 z[0] = n 的，本站统一按 0 处理）。例：s = "aabaa"，则 z = [0, 1, 0, 2, 1]（s[1:]="abaa" 与 s 公共前缀 "a" 长 1；s[3:]="aa" 与 s 公共前缀 "aa" 长 2）。
Z 函数同样靠「维护一个已触及最右的匹配段 [l, r]」（称为 Z-box）来加速：当当前下标 i 落在 Z-box 内（i < r），i 关于 l 的镜像 i - l 的 Z 值已知，可以 min(z[i-l], r-i) 为初值起步扩展；否则从 0 起步。由于 r 单调右移、总推进 ≤ n，Z 数组的构造是 O(n) 的。
构造出 Z 数组后，大量字符串问题迎刃而解：字符串匹配（模式串拼到主串前面加分隔符，z[i] == |pat| 即匹配）、最小周期（z[p] == n - p 则 p 是循环节长度）、重复子串判定等。完整推导与应用见Z 函数（扩展 KMP）。
五、共性：为什么都是 O(n)
Manacher 与 Z 函数虽然解决的问题不同，但线性复杂度的证明完全同构，核心是同一个套路：
- 维护一个「单调右移」的最右右端点：Manacher 是「最右回文右端
R」，Z 函数是「最右匹配段右端r」。 - 当前下标落在已知区间内时，从镜像位置的已知值起步：避免从 0 重新扩展。
- 摊还分析：右端点每右移一次都伴随一次「真正的字符比较」，而右端点总共最多右移 n 次，所以「真正比较」总次数 ≤ n；那些「借用初值、扩展 0 次」的步骤是免费的——总比较 ≤ 2n，O(n)。
理解了这个「单调右端点 + 镜像借用 + 摊还」的三件套，就理解了字符串线性算法的精髓，也为后续学 KMP 的 next 数组、AC 自动机的 fail 指针打下基础。
下一步
理解了回文的定义、朴素 O(n²) 中心扩展与「加速」的动机后，下一步是真正把最长回文子串做到 O(n) 的 Manacher 算法——预处理、p 数组、对称镜像加速一气呵成。