Java中KMP算法怎么實現

Java中KMP算法怎么實現

KMP算法（Knuth-Morris-Pratt算法）是一種用于字符串匹配的高效算法。它的核心思想是通過預處理模式串（pattern），構建一個部分匹配表（也稱為“失敗函數”或“next數組”），從而在匹配過程中避免不必要的回溯。本文將詳細介紹如何在Java中實現KMP算法。

1. KMP算法簡介

KMP算法的主要優勢在于它能夠在O(n + m)的時間復雜度內完成字符串匹配，其中n是文本串的長度，m是模式串的長度。相比于樸素的字符串匹配算法（時間復雜度為O(n * m)），KMP算法在處理長文本串和模式串時具有明顯的性能優勢。

2. KMP算法的核心思想

KMP算法的核心思想是利用模式串的自身信息，避免在匹配失敗時進行不必要的回溯。具體來說，KMP算法通過預處理模式串，構建一個部分匹配表（next數組），該表記錄了模式串中每個位置之前的最長相同前綴和后綴的長度。在匹配過程中，當字符不匹配時，KMP算法會根據next數組的值，將模式串向右移動一定的距離，從而避免從頭開始匹配。

3. KMP算法的實現步驟

3.1 構建next數組

next數組的構建是KMP算法的關鍵步驟。next數組的定義如下：

• next[0] = -1
• next[i] = k，其中k是模式串中前i個字符的最長相同前綴和后綴的長度

構建next數組的過程可以通過以下代碼實現：

public static int[] getNext(String pattern) {
    int[] next = new int[pattern.length()];
    next[0] = -1;
    int i = 0, j = -1;
    while (i < pattern.length() - 1) {
        if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
    return next;
}

3.2 匹配過程

在構建好next數組后，KMP算法的匹配過程如下：

1. 初始化兩個指針i和j，分別指向文本串和模式串的起始位置。
2. 逐個比較文本串和模式串的字符：
   • 如果字符匹配，則繼續比較下一個字符。
   • 如果字符不匹配，則根據next數組的值移動模式串的指針j。
3. 如果模式串的指針j移動到模式串的末尾，則說明匹配成功，返回匹配的起始位置。
4. 如果文本串的指針i移動到文本串的末尾，則說明匹配失敗，返回-1。

匹配過程的Java實現如下：

public static int kmp(String text, String pattern) {
    int[] next = getNext(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;
    }
}

4. 完整代碼示例

以下是一個完整的KMP算法實現示例：

public class KMP {
    public static int[] getNext(String pattern) {
        int[] next = new int[pattern.length()];
        next[0] = -1;
        int i = 0, j = -1;
        while (i < pattern.length() - 1) {
            if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        return next;
    }

    public static int kmp(String text, String pattern) {
        int[] next = getNext(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) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        int index = kmp(text, pattern);
        if (index != -1) {
            System.out.println("Pattern found at index " + index);
        } else {
            System.out.println("Pattern not found");
        }
    }
}

5. 總結

KMP算法通過預處理模式串，構建next數組，從而在匹配過程中避免了不必要的回溯，大大提高了字符串匹配的效率。本文詳細介紹了KMP算法的核心思想、實現步驟，并提供了完整的Java代碼示例。希望本文能幫助你理解并掌握KMP算法的實現。