exkmp（Z 函数）_算法

exkmp（Z 函数）

代码很像 manacher，思路也很像。

作用是求一个串和每个后缀的 $lcp$。

inline void Z(char *s, int n) {
    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, 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;
    }
}

维护 $z_i$，表示 $i$ 开始的后缀与 $1$ 开始的后缀的 $lcp$，在求的过程中我们动态维护 $l,r$ 表示 $r$ 最大的已匹配的 $lcp$。

在求新的 $z$ 的时候，我们直接利用已有信息，将其初始化为 $\min(z_{i-l+1},r-i+1)$，然后暴力匹配即可，由于暴力匹配成功必定会使得 $r$ 变大，所以均摊可证复杂度。

注意 $z_1$ 初始化为 $n$，求 $z$ 时从 $2$ 开始枚举。

同理，我们可以对求出了 $z$ 数组的串与另一个串的每个后缀求 $lcp$。