扩展 KMP/exKMP（Z 函数）学习笔记

shangruolin · 2024-07-16 19:30:05 · 题解

扩展 KMP/exKMP（Z 函数）学习笔记兼 P10479 匹配统计 题解。

LCP：最长公共前缀。

Z 函数，又称扩展 KMP（exKMP），能够在 O(n) 的时间内求出一个字符串与其所有后缀的 LCP 的长度。

定义 z_i 为字符串 s 与字符串 s 从第 i 位开始的后缀的 LCP 长度。

那么求解 z_i 便是我们的目标。直接暴力匹配复杂度为 O(n^2)。二分枚举长度再用哈希判断可以做到 O(n\log n)，足以通过本题。使用 Z 函数求解便可做到 O(n) 求解。

假设现在已经求出了 z_1\sim z_{i-1}，想要求解 z_i。

定义 r 为 r 最大的匹配子串的右端点，l 为 r 最大的匹配子串的左端点。

那么如果 i\le r，z_i 为 \min(z_{i-l+1},r-i+1)。通俗的解释一下：由定义知，s_{l}\sim s_{i-1} 与 s_1\sim s_{i-l} 是匹配的，则