KMP字符串匹配

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，它通过预先计算模式串的部分匹配表（也称为“失败函数”或“next数组”）来避免不必要的回溯，从而提高了搜索效率。KMP算法的时间复杂度为 $O (n + m)$ ，其中 $n$ 是文本串的长度， $m$ 是模式串的长度。

基本思想

KMP算法的关键在于构建一个部分匹配表，这个表记录了模式串中每一个前缀的最大相同后缀的长度。具体来说，部分匹配表是一个数组next，其中next[i]表示模式串的前i个字符中最大的相同前后缀的长度。

部分匹配表的构建

初始化next数组的第一个值为-1。
从第二个位置开始，用两个指针j和k来构建next数组：
- j指向模式串当前位置。
- k指向模式串中前一个最大相同前后缀的位置。
- 如果模式串当前位置的字符与前一个最大相同前后缀后面的字符相等，则将next[j]设为next[k] + 1，并同时递增j和k。
- 如果不相等，则将k回退到next[k]的位置继续比较。
- 如果k为-1，则将next[j]设为0，并仅递增j。

字符串匹配

使用两个指针i和j分别指向文本串和模式串的当前字符。
如果当前字符相等，则同时递增i和j。
如果当前字符不相等，则根据next[j]的值来决定模式串的指针j应该移动到的位置：
- 如果j为0，则仅递增i。
- 否则，将j设置为next[j]的值。

代码实现

查看代码

java

public class KMPAlgorithm {

    /**
     * 构建部分匹配表
     * @param pattern 模式串
     * @return 部分匹配表
     */
    private int[] computeNextArray(String pattern) {
        int[] next = new int[pattern.length()];
        next[0] = -1;
        int j = 0, k = -1;

        while (j < pattern.length() - 1) {
            if (k == -1 || pattern.charAt(j) == pattern.charAt(k)) {
                j++; k++;
                next[j] = (pattern.charAt(j) != pattern.charAt(k)) ? k : next[k];
            } else {
                k = next[k];
            }
        }

        return next;
    }

    /**
     * KMP算法进行字符串匹配
     * @param text 文本串
     * @param pattern 模式串
     * @return 模式串在文本串中的首次出现位置索引，如果没有找到则返回-1
     */
    public int kmpSearch(String text, String pattern) {
        int[] next = computeNextArray(pattern);
        int i = 0, j = 0;

        while (i < text.length() && j < pattern.length()) {
            if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
                i++; j++;
            } else {
                j = next[j];
            }
        }

        if (j >= pattern.length()) {
            return i - j; // 模式串的起始位置
        } else {
            return -1; // 没有找到模式串
        }
    }

    public static void main(String[] args) {
        KMPAlgorithm kmp = new KMPAlgorithm();
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";

        int index = kmp.kmpSearch(text, pattern);
        if (index != -1) {
            System.out.println("模式串 '" + pattern + "' 在文本串 '" + text + "' 中的位置: " + index);
        } else {
            System.out.println("模式串 '" + pattern + "' 没有出现在文本串 '" + text + "' 中。");
        }
    }
}

代码解释

构建部分匹配表：computeNextArray方法用于计算模式串的部分匹配表。该方法从模式串的第一个字符开始，通过比较前后缀来填充next数组。
字符串匹配：kmpSearch方法使用部分匹配表来进行字符串匹配。通过两个指针i和j分别遍历文本串和模式串，当遇到不匹配时，根据next数组调整模式串的指针位置。
主程序：main方法定义了文本串和模式串，并调用kmpSearch方法来查找模式串在文本串中的位置。

KMP字符串匹配 ​

基本思想 ​

部分匹配表的构建 ​

字符串匹配 ​

代码实现 ​

代码解释 ​