概述
对于字符串 $s$，记 $z_i$ 为 $i$ 后缀与 $s$ 的最长公共前缀。exKMP 算法可以 $O(n)$ 求 $z$。
记 $[i,i+z_i-1]$ 为匹配段，在求解过程中维护最靠右的匹配段 $[l,r]$，当求解 $z_i$ 时。
$r < i$ 暴力匹配。
$i \le r$ 令 $z_i=\min(r-i+1,z_{i-l+1})$，再暴力匹配。
均摊线性。
$[1,z_1]$ 是没有意义的，不要计入 $[l,r]$。
例题
1.【模板】扩展 KMP/exKMP（Z 函数）
构造 $b+!+a$。需要特判 $z_1$。
2.Prefixes and Suffixes
完美字串是好找的，需要计算每个前缀的出现次数，计算 $z$，每次 $[1,z_i]$ 区间加 $1$。时间复杂度 $O(n)$。
3.Om Nom and Necklace
相当于 $S=AA…AB$，$A$ 有 $k$ 个，$B$ 为 $A$ 的前缀。