如何使用java實作Boyer-Moore演算法

如何使用Java實作Boyer-Moore演算法

引言：
在電腦科學中，字串比對是一項常見的任務。而字串匹配演算法是解決這問題的關鍵。其中一種高效率的字串比對演算法就是Boyer-Moore演算法。本文將介紹如何使用Java語言來實作此演算法，並附上具體的程式碼範例。

Boyer-Moore演算法的原理：
Boyer-Moore演算法是一種多模式串匹配演算法，它透過對模式串的預處理，結合好後綴規則和壞字元規則來完成匹配。其核心思想是在模式串和待匹配串的匹配過程中，盡可能地跳過不匹配的字符，從而提高匹配效率。

具體實作步驟：

1. 預處理模式字串：
   首先，我們需要對模式字串進行預處理，產生兩個陣列：壞字元陣列和好後綴數組。

   • 壞字元陣列：儲存每個字元在模式字串中最右邊出現的位置。
   • 好後綴陣列：記錄模式字串的後綴子字串在模式字串中的最右出現位置，並且記錄這個子字串是否與模式字串的前綴相符。

2. 符合過程：
   在符合過程中，我們從待匹配字串的結尾開始向前配對。

   • 首先，將模式字串的末尾與待匹配串的末尾對齊，並嘗試匹配。
   • 如果匹配成功，則傳回符合的起始位置，否則根據壞字元和好後綴規則移動模式字串的位置繼續匹配。

具體程式碼如下：

import java.util.Arrays;

public class BoyerMoore {

    private static final int NO_OF_CHARS = 256;

    private int[] badCharShift;
    private int[] suffixShift;
    private boolean[] goodSuffix;

    public void preProcessPattern(String pattern) {
        int m = pattern.length();
        // 初始化数组
        badCharShift = new int[NO_OF_CHARS];
        suffixShift = new int[m + 1];
        goodSuffix = new boolean[m + 1];

        Arrays.fill(badCharShift, -1);
        for (int i = 0; i < m; i++) {
            badCharShift[pattern.charAt(i)] = i;
        }

        int f = 0;
        int g = 0;
        suffixShift[m] = m + 1;

        for (int i = m - 1; i >= 0; i--) {
            if (i > f && suffixShift[i + m - f] < i - f) {
                suffixShift[i] = suffixShift[i + m - f];
            } else {
                if (i < f) {
                    f = i;
                }
                g = i;
                while (f >= 0 && pattern.charAt(f) == pattern.charAt(f + m - g)) {
                    f--;
                }
                suffixShift[i] = g - f;
            }
        }

        for (int i = 0; i < m; i++) {
            goodSuffix[i] = suffixShift[i] > m - i;
        }
    }

    public int search(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int i = 0;

        while (i <= n - m) {
            int j = m - 1;
            while (j >= 0 && pattern.charAt(j) == text.charAt(i + j)) {
                j--;
            }
            if (j < 0) {
                return i; // 匹配成功，返回匹配位置
            } else {
                i += Math.max(goodSuffix[j + 1], j - badCharShift[text.charAt(i + j)]);
            }
        }
        return -1; // 未匹配成功，返回-1
    }

    public static void main(String[] args) {
        BoyerMoore bm = new BoyerMoore();
        String text = "This is a test";
        String pattern = "test";
        bm.preProcessPattern(pattern);
        int index = bm.search(text, pattern);
        if (index != -1) {
            System.out.println("Pattern found at index: " + index);
        } else {
            System.out.println("Pattern not found");
        }
    }
}

總結：
本文介紹如何使用Java語言來實作Boyer-Moore演算法，並透過具體的程式碼範例展示了演算法的使用過程。 Boyer-Moore演算法在字串匹配領域擁有很高的效率和廣泛的應用，透過合理利用好後綴和壞字元規則，可以大大提高字串匹配的效率。希望本文對您理解並實踐Boyer-Moore演算法有所幫助。

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