简介

exKMP（扩展 KMP 算法），也叫 Z algorithm（Z 算法），可以在 \(\mathcal{O}(|s|+|t|)\) 求解文本串 \(s\) 的所有后缀与匹配串 \(t\) 的最长公共前缀（LCP）。

实现

定义一个长度为 \(n\) 的字符串 \(s\) 的 \(z\) 函数 \(z_i\) 表示 \(s\) 长度为 \(i\) 的后缀与自身的最长公共前缀的长度。一般情况下令 \(z_1 = 0\)。

称 \([i,i + z_i - 1]\) 为 \(i\) 这个位置的匹配段，也可以称作 z-box。根据定义，\(s[i,i + z_i - 1] = s[1,z_i]\)。算法实现中，我们要记录最靠右的匹配段 \([l,r]\)，初始 \(l = r = 0\)。

当我们匹配到一个位置 \(i\) 时，需进行分类讨论：

1. 若 \(i > r\)，直接暴力匹配计算 z 函数。
2. 反之，因为 \(s[1,r - l + 1] = s[l,r]\)，所以 \(s[i,r] = s[i - l + 1,r - l + 1]\)。所以先令 \(z_i = \min(r - i + 1,z_{i - l + 1})\)，再暴力计算。

复杂度显然线性。

for (int i = 2,l = 0,r = 0;i <= n;i++) {
	z[i] = i > r ? 0 : min(r - i + 1, z[i - l + 1]);
	while (t[1 + z[i]] == t[i + z[i]]) z[i]++;
	if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
}