如何使用java實作字串匹配演算法

如何使用Java實作字串比對演算法

引言：
字串比對演算法是電腦領域中常見的問題，用於在一個主串中尋找特定模式串的出現位置。在實際開發中，經常需要對字串進行匹配，例如文字編輯器中的查找功能，搜尋引擎中的關鍵字匹配等等。本文將介紹幾種常見的字串比對演算法，並提供對應的Java程式碼範例。

一、暴力比對演算法
暴力比對演算法，又稱樸素比對演算法，是最基本的字串比對演算法。它的原理非常簡單，即從主串中的每一個位置開始，與模式串進行逐個字元的比較，直到出現不匹配的字元或成功找到匹配。

具體實現代碼如下：

public class BruteForceMatcher {
    public int match(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        for (int i = 0; i <= n - m; i++) {
            int j;
            for (j = 0; j < m; j++) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    break;
                }
            }
            if (j == m) {
                return i;
            }
        }
        return -1;
    }
}

二、KMP演算法
KMP演算法是一種高效的字串匹配演算法，它利用了模式串的部分匹配信息，避免了不必要的字元比較。 KMP演算法的核心是建立一個next數組，用於記錄模式串中每個位置的最長公共前後綴的長度。

具體實作程式碼如下：

public class KMPMatcher {
    public int match(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int[] next = getNext(pattern);
        int i = 0, j = 0;
        while (i < n && j < m) {
            if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j == m) {
            return i - j;
        } else {
            return -1;
        }
    }

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

三、Boyer-Moore演算法
Boyer-Moore演算法是一種高效的字串比對演算法，利用了模式串中的字元分佈訊息和後移規則。

具體實作程式碼如下：

public class BMMatcher {
    public int match(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int[] bmBc = preBmBc(pattern);
        int[] bmGs = preBmGs(pattern);
        int j = 0;
        while (j <= n - m) {
            int i;
            for (i = m - 1; i >= 0 && pattern.charAt(i) == text.charAt(i + j); i--);
            if (i < 0) {
                return j;
            } else {
                j += Math.max(bmGs[i], bmBc[text.charAt(i + j)] - m + 1 + i);
            }
        }
        return -1;
    }

    private int[] preBmBc(String pattern) {
        int[] bmBc = new int[256];
        int m = pattern.length();
        for (int i = 0; i < 256; i++) {
            bmBc[i] = m;
        }
        for (int i = 0; i < m - 1; i++) {
            bmBc[pattern.charAt(i)] = m - 1 - i;
        }
        return bmBc;
    }

    private int[] preBmGs(String pattern) {
        int m = pattern.length();
        int[] bmGs = new int[m];
        int i = m - 1, j = m;
        bmGs[m - 1] = m;
        while (i >= 0) {
            if (pattern.charAt(i) == pattern.charAt(j)) {
                bmGs[--i] = --j;
            } else {
                j = m - 1 - i;
                while (j < m && pattern.charAt(m - 1 - j) == pattern.charAt(j)) {
                    j++;
                }
                bmGs[i] = j;
            }
        }
        return bmGs;
    }
}

結論：
以上是三種常見的字串比對演算法的程式碼範例，它們分別是暴力比對演算法、KMP演算法和Boyer-Moore演算法.在實際應用中，可以根據具體需求選擇合適的演算法，以提高配對效率。

以上是如何使用java實作字串匹配演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！