Z 算法原理与 Java 实现

1
import java.util.Arrays;
2

3
public class ZAlgorithm {
4

5
    /**
6
     * 计算字符串的 Z 数组
7
     *
8
     * @param s 输入字符串
9
     * @return z 数组，z[i] 表示后缀 s[i...] 与 s 的最长公共前缀长度
10
     */
11
    public static int[] zFunction(String s) {
12
        int n = s.length();
13
        int[] z = new int[n];
14

15
        // l 和 r 维护当前的 Z-box，即区间 [l, r]
16
        // 初始时 l = r = 0
17
        for (int i = 1, l = 0, r = 0; i < n; ++i) {
18
            // 情况 2：当前位置 i 在 Z-box 内 (i <= r)
19
            // 我们可以利用已知的 z[i - l] 来初始化 z[i]
20
            // min 的作用是防止访问越过当前的 Z-box (即不超过 r - i + 1)
21
            if (i <= r) {
22
                z[i] = Math.min(r - i + 1, z[i - l]);
23
            }
24

25
            // 尝试向后扩展匹配 (朴素比较)
26
            // 无论是由情况 1 (i > r) 进入，还是情况 2 中初始化后继续尝试，都通过此循环处理
27
            while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) {
28
                z[i]++;
29
            }
30

31
            // 如果匹配延伸超过了当前的 r，更新 Z-box 的边界
32
            if (i + z[i] - 1 > r) {
33
                l = i;
34
                r = i + z[i] - 1;
35
            }
36
        }
37
        return z;
38
    }
39

40
    public static void main(String[] args) {
41
        String s = "aabcaabxaa";
42
        int[] z = zFunction(s);
43

44
        System.out.println("String: " + s);
45
        System.out.println("Z-array: " + Arrays.toString(z));
46

47
        // 简单测试模式匹配应用
48
        // 查找 pattern "aab" 在 text "baabaa" 中的位置
49
        // 构造 S = P + "$" + T -> "aab$baabaa"
50
        String pattern = "aab";
51
        String text = "baabaa";
52
        String concat = pattern + "$" + text;
53
        int[] zConcat = zFunction(concat);
54

55
        System.out.println("\nPattern Matching Example:");
56
        System.out.println("Combined String: " + concat);
57
        for (int i = 0; i < zConcat.length; i++) {
58
            // 如果某位置的 Z 值等于模式串长度，说明匹配成功
59
            if (zConcat[i] == pattern.length()) {
60
                // 计算在原文本中的索引
61
                // i - (pattern.length() + 1)
62
                System.out.println("Pattern found at index: " + (i - pattern.length() - 1));
63
            }
64
        }
65
    }
66
}