Z函数

定义z[i]表示𝑠[i:]与𝑠的LCP（最长公共前缀）的长度，其中𝑠[i:]表示从𝑠[i]到𝑠[n−1]的子串（后缀串）

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private int[] calcZ(int[] s, int start) {
    int n = s.length - start;
    int[] z = new int[n];
    int boxL = 0;
    int boxR = 0; // z-box 左右边界
    for (int i = 1; i < n; i++) {
        if (i <= boxR) {
            z[i] = Math.min(z[i - boxL], boxR - i + 1);
        }
        while (i + z[i] < n && s[start + z[i]] == s[start + i + z[i]]) {
            boxL = i;
            boxR = i + z[i];
            z[i]++;
        }
    }
    return z;
}

举例：Z 数组对于 “abacaba” 是：[0, 0, 1, 0, 3, 0, 1]

注意：按定义来说，z[0]应该是7，看情况，用不用的到z[0]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
i = 1：

i > boxR，进入while循环。
s[0] != s[1]，z[1]保持为0。
boxL和boxR不变。
i = 2：

i > boxR，进入while循环。
s[0] == s[2]，z[2]++，z[2] = 1。
更新boxL = 2，boxR = 2。
i = 3：

i > boxR，进入while循环。
s[0] != s[3]，z[3]保持为0。
boxL和boxR不变。
i = 4：

i > boxR，进入while循环。
s[0] == s[4]，z[4]++，z[4] = 1。
s[1] == s[5]，z[4]++，z[4] = 2。
s[2] == s[6]，z[4]++，z[4] = 3。
更新boxL = 4，boxR = 6。
i = 5：

i <= boxR，z[5] = Math.min(z[1], boxR - i + 1) = Math.min(0, 2) = 0。
s[0] != s[5]，z[5]保持为0。
boxL和boxR不变。
i = 6：

i <= boxR，z[6] = Math.min(z[2], boxR - i + 1) = Math.min(1, 1) = 1。
s[1] != s[7]（超出范围），z[6]保持为1。
boxL和boxR不变。
最终结果：z = [0, 0, 1, 0, 3, 0, 1]