Java中 String 字符串匹配 KMP 算法怎么在 Java 中实现-java教程-PHP中文网

kmp算法通过构建next数组实现高效字符串匹配，时间复杂度o(n+m)；next[i]表示pattern[0..i]最长相等真前缀与真后缀长度，构建时用双指针法，匹配时主串指针i不回退。

java中 string 字符串匹配 kmp 算法怎么在 java 中实现

KMP（Knuth-Morris-Pratt）算法是字符串匹配的经典高效算法，核心在于预处理模式串（pattern），构建 next 数组（也叫 failure function 或 lps 数组），避免主串指针回退，实现 O(n + m) 时间复杂度。

理解 next 数组的含义

next[i] 表示 pattern[0..i] 的最长相等真前缀与真后缀的长度。例如 pattern = "ababca"，next 数组为 [0,0,0,1,2,0]。它决定了当匹配失败时，模式串该往右滑多少位——不是回到开头，而是跳到能复用已匹配部分的位置。

next[0] 固定为 0（单字符无真前后缀）
构建时用双指针：j 指向前缀末尾，i 遍历后缀末尾；若 pattern[i] == pattern[j]，则 j++，next[i] = j；否则 j 回退到 next[j-1]，继续比较

Java 中构建 next 数组

以下是一个清晰、无歧义的 next 数组构造方法：

Java JDK 25

Java JDK 25 来自 OpenJDK 官方归档，版本为 JDK 25，本条下载地址已指向官方 Windows x64 zip 安装包直链，适合调试旧项目或兼容旧版 Java 运行环境。

下载

<font size="2">private static int[] buildNext(String pattern) {
    int n = pattern.length();
    int[] next = new int[n];
    for (int i = 1, j = 0; i  0 && pattern.charAt(i) != pattern.charAt(j)) {
            j = next[j - 1];
        }
        if (pattern.charAt(i) == pattern.charAt(j)) {
            j++;
        }
        next[i] = j;
    }
    return next;
}</font>

执行 KMP 匹配主逻辑

用两个指针 i（主串索引）、j（模式串索引）遍历。匹配成功时返回首次出现下标；失败时依据 next[j-1] 调整 j，i 不回退。

<font size="2">public static int kmpSearch(String text, String pattern) {
    if (pattern.isEmpty()) return 0;
    if (text.length() int[] next = buildNext(pattern);
for (int i = 0, j = 0; i  0 && text.charAt(i) != pattern.charAt(j)) {
        j = next[j - 1];
    }
    if (text.charAt(i) == pattern.charAt(j)) {
        j++;
    }
    if (j == pattern.length()) {
        return i - j + 1; // 匹配起始位置
    }
}
return -1;</font>

}

使用示例与注意事项

调用方式简单：

<font size="2">String text = "ababababca";
String pattern = "ababc";
int pos = kmpSearch(text, pattern); // 返回 2</font>

边界情况要覆盖：空 pattern、pattern 比 text 长、完全不匹配
next 数组构建和匹配过程都只需一趟扫描，空间复杂度 O(m)
注意 charAt() 索引安全，但上述代码已确保 j ≥ 0 且 i 在合法范围内

Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南