Z 函数 / exKMP
stripe_python · · 算法·理论
问题 给定字符串
二分哈希或者 SA 容易做到 1log。
称
- 若
i>r ,向后暴力扩展。 - 若
i \le r ,根据 LCP 对称性,考察z[i-l+1] 再暴力扩展。
复杂度均摊线性。
void exkmp() {
z[1] = n;
for (int i = 2, l = 1, r = 1; i <= n; i++) {
z[i] = i > r ? 0 : min(z[i-l+1], r-i+1);
while (i+z[i] <= n && s[z[i]+1] == s[z[i]+i]) z[i]++;
if (i+z[i]-1 > r) l = i, r = i+z[i]-1;
}
}