Z 函数 / exKMP

· · 算法·理论

问题 给定字符串 S,对每个 i 求出 z[i]=\text{lcp}(S,S[i:n])。

二分哈希或者 SA 容易做到 1log。

称 [i,i+z[i]-1] 为匹配段。顺序扫描 i=1\to n,维护最右匹配段 [l,r]。

复杂度均摊线性。

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;
    }
}