exKMP
概念
对于一个长度为 \(n\) 的字符串 \(s\)。定义函数 \(z_i\) 表示 \(s\) 与 \(s[i, n - 1]\) 的最长公共前缀的长度， \(z\) 被称为 \(s\) 的Z函数
特别地， \(z_0 = 0\)
实现
对于 \(i\) ，我们称区间 \([i, i + z[i] - 1]\) 为 \(i\) 的匹配段，亦称Z-box
考虑维护右端点最靠右的匹配段，记作 \([l, r]\) 。根据定义， \(s[l, r]\) 是 \(s\) 的前缀。在计算 \(z_i\) 时我们保证 \(l \leq i\) ，初始时 \(l = r = 0\)
过程：
- 若 \(i \leq r\) ，则有 \(s[i, r] = s[i - l, r - l]\) ，因此 \(z_i \geq \min(z_{i - l}, r - i + 1)\) ，此时
- 若 \(z[i - l] < r - i + 1\) 则 \(z_i = z_{i - l}\)
- 否则， \(z_{i - l} \geq r - i + 1\) ，令 \(z_i = r - i + 1\) 然后暴力枚举下一位匹配到无法拓展为止
- 若 \(i > r\) ，那么直接暴力枚举下一位匹配到无法拓展为止
inline void GetFunctionZ(string str) {
for (int i = 1, l = 0, r = 0; i < str.length(); ++i) {
if (i <= r && z[i - l] < r - i + 1)
z[i] = z[i - l];
else {
z[i] = max(0, r - i + 1);
while (i + z[i] < str.length() && str[i + z[i]] == str[z[i]])
++z[i];
}
if (i + z[i] - 1 > r)
l = i, r = i + z[i] - 1;
}
}