Z 函数 学习笔记

作者: xht37 分类: 笔记 发布时间: 2020-02-21 15:11

点击数:155

Z 函数,又称扩展 KMP (exkmp),可以 $\mathcal O(n)$ 求出一个字符串的所有后缀与这个字符串的 LCP 长度。

定义 $z$ 函数

对于字符串 $s$,$z_i$ 定义为 $|\operatorname{LCP}(s, s[i:])|$,即从 $i$ 开始的后缀与 $s$ 的最长公共子串的长度。

暴力求显然是 $\mathcal O(n^2)$ 的,通常这个时间复杂度都无法被接受。

$\mathcal O(n)$ 求 $z$ 函数。

维护 $r$ 最大的匹配子串 $s[l:r]$。

当 $i \le r$ 时,我们充分利用已经算出来的 $z$,直接把 $z_i$ 初始化为 $\min(z_{i-l+1}, r – i + 1)$;否则初始化为 $0$。

然后暴力往后匹配得到 $z_i$ 的最终值,若 $i+z_i-1 > r$,还要更新 $l,r$。

这样做时间复杂度是 $\mathcal O(n)$ 的,因为每个字符最多被暴力匹配一次。

注意 $z_1$ 必须单独处理。

inline void Z(char *s, int n) {
    for (int i = 1; i <= n; i++) z[i] = 0;
    z[1] = n;
    for (int i = 2, l = 0, r = 0; i <= n; i++) {
        if (i <= r) z[i] = min(z[i-l+1], r - i + 1);
        while (i + z[i] <= n && s[i+z[i]] == s[z[i]+1]) ++z[i];
        if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
}

【模板】P5410 【模板】扩展 KMP(Z 函数)

const int N = 2e7 + 7;
int n, m, z[N], p[N];
char a[N], b[N];

inline void Z(char *s, int n) {
    for (int i = 1; i <= n; i++) z[i] = 0;
    z[1] = n;
    for (int i = 2, l = 0, r = 0; i <= n; i++) {
        if (i <= r) z[i] = min(z[i-l+1], r - i + 1);
        while (i + z[i] <= n && s[i+z[i]] == s[z[i]+1]) ++z[i];
        if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
}

inline void exkmp(char *s, int n, char *t, int m) {
    Z(t, m);
    for (int i = 1; i <= n; i++) p[i] = 0;
    for (int i = 1, l = 0, r = 0; i <= n; i++) {
        if (i <= r) p[i] = min(z[i-l+1], r - i + 1);
        while (i + p[i] <= n && s[i+p[i]] == t[p[i]+1]) ++p[i];
        if (i + p[i] - 1 > r) l = i, r = i + p[i] - 1;
    }
}

int main() {
    rds(a, n), rds(b, m);
    exkmp(a, n, b, m);
    ll ans = 0;
    for (int i = 1; i <= m; i++) ans ^= 1ll * i * (z[i] + 1);
    print(ans);
    ans = 0;
    for (int i = 1; i <= n; i++) ans ^= 1ll * i * (p[i] + 1);
    print(ans);
    return 0;
}

【练习】CF126B Password

const int N = 1e6 + 7;
int n, z[N], v[N];
char a[N];

inline void Z(char *s, int n) {
    for (int i = 1; i <= n; i++) z[i] = 0;
    z[1] = n;
    for (int i = 2, l = 0, r = 0; i <= n; i++) {
        if (i <= r) z[i] = min(z[i-l+1], r - i + 1);
        while (i + z[i] <= n && s[i+z[i]] == s[z[i]+1]) ++z[i];
        if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
}

int main() {
    rds(a, n);
    Z(a, n);
    for (int i = 2; i <= n; i++)
        if (!v[z[i]]) {
            while (!v[z[i]]) v[z[i]--] = 1;
        } else if (i + z[i] - 1 == n) {
            while (i <= n) putchar(a[i++]);
            return 0;
        }
    prints("Just a legend");
    return 0;
}

【练习】CF432D Prefixes and Suffixes

const int N = 1e5 + 7;
int n, z[N], c[N], ans[N];
char a[N];

inline void add(int x, int k) {
    while (x <= n) c[x] += k, x += x & -x;
}

inline int ask(int x) {
    int k = 0;
    while (x) k += c[x], x -= x & -x;
    return k;
}

inline void Z(char *s, int n) {
    for (int i = 1; i <= n; i++) z[i] = 0;
    z[1] = n;
    for (int i = 2, l = 0, r = 0; i <= n; i++) {
        if (i <= r) z[i] = min(z[i-l+1], r - i + 1);
        while (i + z[i] <= n && s[i+z[i]] == s[z[i]+1]) ++z[i];
        if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
}

int main() {
    rds(a, n);
    Z(a, n);
    for (int i = 1; i <= n; i++) {
        add(1, 1), add(z[i] + 1, -1);
        if (i + z[i] - 1 == n) ans[z[i]] = ask(z[i]), ++ans[0];
    }
    print(ans[0]);
    for (int i = 1; i <= n; i++)
        if (ans[i]) print(i, ' '), print(ans[i]);
    return 0;
}

参考资料

发表评论

电子邮件地址不会被公开。 必填项已用*标注