Z函数（Z-Algorithm，常与扩展KMP关联）和 Manacher 算法都是字符串处理中用于高效匹配和查

找子串的经典线性时间复杂度算法。虽然它们的应用场景有所不同，但核心思想都涉及利用已计算的

信息来避免重复比较从而将复杂度降至 

𝑂

(

𝑛

)

O(n)。

以下是对这两种算法的详细解析及对比：

1. Z函数 (Z-Function)

Z函数通常用于解决字符串前缀匹配问题，也是实现“扩展KMP”（ExKMP）的基础。

定义

对于一个长度为 

𝑛

n 的字符串 

𝑆

S，其 Z函数数组 

𝑍

[

𝑖

]

Z[i] 定义为：子串 

𝑆

[

𝑖

…

𝑛

−

1

]

S[i…n−1] 与字符串 

𝑆

S 本身的最长公共前缀（LCP, Longest Common Prefix）的长度。

通常规定 

𝑍

=

0

Z=0 或 

𝑍

=

𝑛

Z=n（具体取决于实现习惯，一般算法竞赛中常设 

𝑍

=

0

Z=0 或不定义，重点在于 

𝑖

>

0

i>0 的情况）。

核心逻辑：Z-Box

为了在 

𝑂

(

𝑛

)

O(n) 时间内计算所有 

𝑍

[

𝑖

]

Z[i]，算法维护一个“Z-Box”区间 

[

𝑙

,

𝑟

]

[l,r]，表示当前已知的、右端点 

𝑟

r 最靠右的一个匹配区间。即 

𝑆

[

𝑙

…

𝑟

]

S[l…r] 是 

𝑆

S 的前缀 

𝑆

[

0

…

𝑟

−

𝑙

]

S[0…r−l]。

计算 

𝑍

[

𝑖

]

Z[i] 时分为两种情况：

𝑖

>

𝑟

i>r（在 Z-Box 之外）‌：

无法利用之前的信息，必须暴力从 

𝑆

[

𝑖

]

S[i] 和 

𝑆

S 开始逐个字符比较，直到失配。

更新 

𝑙

=

𝑖

,

𝑟

=

𝑖

+

𝑍

[

𝑖

]

−

1

l=i,r=i+Z[i]−1。

𝑖

≤

𝑟

i≤r（在 Z-Box 之内）‌：

利用对称性。令 

𝑘

=

𝑖

−

𝑙

k=i−l，则 

𝑆

[

𝑖

]

S[i] 对应于前缀中的 

𝑆

[

𝑘

]

S[k]。

已知 

𝑆

[

𝑙

…

𝑟

]

S[l…r] 匹配 

𝑆

[

0

…

𝑟

−

𝑙

]

S[0…r−l]，所以 

𝑆

[

𝑖

…

𝑟

]

S[i…r] 匹配 

𝑆

[

𝑘

…

𝑟

−

𝑙

]

S[k…r−l]。

此时 

𝑍

[

𝑖

]

Z[i] 至少为 

min

⁡

(

𝑍

[

𝑘

]

,

𝑟

−

𝑖

+

1

)

min(Z[k],r−i+1)。

若 

𝑍

[

𝑘

]

<

𝑟

−

𝑖

+

1

Z[k]<r−i+1，则 

𝑍

[

𝑖

]

=

𝑍

[

𝑘

]

Z[i]=Z[k]（因为后续字符必然不匹配，否则 

𝑍

[

𝑘

]

Z[k] 会更大）。

若 

𝑍

[

𝑘

]

≥

𝑟

−

𝑖

+

1

Z[k]≥r−i+1，则 

𝑍

[

𝑖

]

Z[i] 至少为 

𝑟

−

𝑖

+

1

r−i+1，需要继续从 

𝑟

+

1

r+1 开始暴力扩展比较，并更新 Z-Box。

应用场景

字符串匹配‌：构造字符串 

𝑃

+

#

+

𝑇

P+#+T（模式串+分隔符+文本串），计算 Z 函数。若某位置 

𝑖

i 的 

𝑍

[

𝑖

]

Z[i] 等于模式串长度 

∣

𝑃

∣

∣P∣，则说明在该位置发生了匹配。

寻找最小循环节‌：通过 Z 函数判断字符串是否具有周期性。

扩展 KMP (ExKMP)‌：用于计算模式串 

𝑃

P 与文本串 

𝑇

T 的每个后缀的最长公共前缀。

2. Manacher 算法 (马拉车算法)

Manacher 算法专门用于解决‌最长回文子串‌问题，将时间复杂度从暴力的 

𝑂

(

𝑛

2

)

O(n

2

) 优化到了 

𝑂

(

𝑛

)

O(n)。

预处理：统一奇偶长度

回文串中心可能在字符上（奇数长度，如 "aba"）或在字符间隙（偶数长度，如 "abba"）。为了统一处理，

Manacher 算法会在原字符串的每个字符之间以及首尾插入特殊字符（如 #）。

原串: aba -> 新串: #a#b#a#

原串: abba -> 新串: #a#b#b#a#

这样，所有回文子串在新串中都变成了以某个字符为中心的‌奇数长度‌回文串。

核心逻辑：回文半径数组 

𝑃

P

定义数组 

𝑃

[

𝑖

]

P[i] 为新串中以 

𝑖

i 为中心的最长回文半径（包含中心字符本身）。例如，若新串中回文串为 #a#，中心在 a，半径为 2

（覆盖 #a# 三个字符，通常定义半径为回文串长度的一半向下取整+1，或者直接定义为回文串总长度，

具体视实现而定，常见定义是 

𝑃

[

𝑖

]

P[i] 为以 

𝑖

i 为中心向右扩展的最大步数+1，即回文串总长度为 

2

⋅

𝑃

[

𝑖

]

−

1

2⋅P[i]−1）。

算法同样维护一个当前右边界最远的回文中心 

𝐶

C 和其右边界 

𝑅

R。对于当前位置 

𝑖

i：

𝑖

>

𝑅

i>R（在当前最右回文边界之外）‌：

无法利用对称性，初始 

𝑃

[

𝑖

]

=

1

P[i]=1，然后向两边暴力扩展。

𝑖

≤

𝑅

i≤R（在当前最右回文边界之内）‌：

找到 

𝑖

i 关于中心 

𝐶

C 的对称位置 

𝑗

=

2

𝐶

−

𝑖

j=2C−i。

利用回文的对称性，

𝑃

[

𝑖

]

P[i] 至少为 

min

⁡

(

𝑃

[

𝑗

]

,

𝑅

−

𝑖

)

min(P[j],R−i)。

若 

𝑃

[

𝑗

]

<

𝑅

−

𝑖

P[j]<R−i，说明以 

𝑗

j 为中心的回文串完全包含在以 

𝐶

C 为中心的大回文串内部，根据对称性，

𝑃

[

𝑖

]

=

𝑃

[

𝑗

]

P[i]=P[j]。

若 

𝑃

[

𝑗

]

≥

𝑅

−

𝑖

P[j]≥R−i，说明以 

𝑗

j 为中心的回文串触及或超出了大回文串的左边界，此时 

𝑃

[

𝑖

]

P[i] 至少为 

𝑅

−

𝑖

R−i，需要以 

𝑅

R 为起点继续向右边暴力扩展，并更新 

𝐶

C 和 

𝑅

R。

结果还原

新串中的最长回文半径 

𝑚

𝑎

𝑥

(

𝑃

[

𝑖

]

)

max(P[i]) 对应原串中最长回文子串的长度。

若新串中回文半径为 

𝑙

𝑒

𝑛

len，则原串中对应的回文长度为 

𝑙

𝑒

𝑛

−

1

len−1。

3. 两者对比与总结

表格

特性 Z函数 (Z-Algorithm) Manacher 算法

主要用途‌ 前缀匹配、字符串搜索、周期检测 最长回文子串查找

核心思想‌ 利用已匹配的‌前缀‌区间 (Z-Box) 加速后续匹配 利用已计算的‌回文‌对称性加速后续半径计算

时间复杂度‌

𝑂

(

𝑛

)

O(n)

𝑂

(

𝑛

)

O(n)

空间复杂度‌

𝑂

(

𝑛

)

O(n)

𝑂

(

𝑛

)

O(n)

关键技巧‌ 维护最右匹配边界 

[

𝑙

,

𝑟

]

[l,r]，利用 

𝑆

[

𝑖

]

S[i] 与 

𝑆

[

𝑖

−

𝑙

]

S[i−l] 的关系 维护最右回文边界 

[

𝐶

−

𝑅

,

𝐶

+

𝑅

]

[C−R,C+R]，利用对称点 

2

𝐶

−

𝑖

2C−i 的值

预处理‌ 通常需要将模式串和文本串拼接 需要插入分隔符以统一奇偶回文

共同点

线性复杂度‌：两者都通过维护一个“最右边界”，确保每个字符最多被暴力比较一次，从而保证整体 

𝑂

(

𝑛

)

O(n) 的复杂度。

利用历史信息‌：都不是从头开始盲目比较，而是先根据之前计算出的区间信息给出一个“初始估计值”，只有在必要时才进行额外的暴力扩展。

选择建议

如果你需要查找一个模式串在文本串中出现的所有位置，或者计算两个字符串的最长公共前缀，使用 ‌Z函数‌ 或 ‌扩展KMP‌。

如果你需要在一个字符串中找到最长的回文子串，‌Manacher 算法‌ 是最优解。