您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java 資料結構與演算法：暴力字串匹配 Brute Force 完整實作與複雜度分析

編輯：Java 相關知識

演算法核心思想

暴力匹配（Brute Force）採用 雙層迴圈 滑動比對：外層迴圈枚舉主串起始位置，內層迴圈逐字元比對模式串。失配時，主串起始位置右移一格，模式串重頭開始比對。

標準實作

package al;

public class BruteForce {
    /**
     * 暴力字串匹配
     * @param text 主串（待搜尋文本）
     * @param pattern 模式串
     * @return 首次匹配成功的起始索引（0-based），失敗返回 -1
     * 時間複雜度：O(m*n) — m=pattern長度, n=text長度
     * 空間複雜度：O(1)
     */
    public int search(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();

        if (m == 0) return 0; // 空模式串匹配任意位置
        if (n < m) return -1; // 主串比模式串短，不可能匹配

        // 外層：主串每個可能的起始位置
        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; // 失配，跳出內層
                }
            }
            // 內層正常結束（j == m）表示完全匹配
            if (j == m) {
                return i;
            }
        }
        return -1; // 遍歷完無匹配
    }

    public static void main(String[] args) {
        BruteForce bf = new BruteForce();
        String text = "abbacbabcdabcbec";
        String pattern = "abcbe";

        int index = bf.search(text, pattern);
        System.out.println("主串：" + text);
        System.out.println("模式：" + pattern);
        System.out.println("匹配索引：" + index); // 輸出：10
        if (index >= 0) {
            System.out.println("驗證子串：" + text.substring(index, index + pattern.length()));
        }
    }
}

執行過程圖解（text="ABCABD", pattern="ABD"）

i=0: A B C A B D
       A B D     → 第3字元 C≠D 失配

i=1: A B C A B D
         A B D   → 第1字元 B≠A 失配

i=2: A B C A B D
           A B D → 第1字元 C≠A 失配

i=3: A B C A B D
             A B D → 完全匹配！返回 3

複雜度分析

情況	時間複雜度	說明
最壞情況	O(m*n)	模式串重複子串頻繁出現於主串（如 text="AAAAA", pattern="AAA"）
最佳情況	O(n)	首字元即失配，內層迴圈常數次結束
平均情況	O(n+m)	隨機字串下，失配極快，接近線性
空間複雜度	O(1)	僅使用常數額外變數

優缺點總結

優點	缺點
算法簡單，易理解、易實作、易除錯	最壞情況 O(m*n) 效能差
無需預處理，適合單次搜尋、短模式串	大量回溯（主串指標隱性後退），資訊未利用
短文本、低頻搜尋實務表現往往優於複雜算法	不適用於高頻、長文本、多模式搜尋

進階演算法演進

暴力匹配的核心缺陷是 失配後資訊浪費。後續經典算法針對此優化：

KMP (Knuth-Morris-Pratt)：預處理模式串構建 next[]（部分匹配表），失配時模式串不回溯，主串指標不回退 → O(n+m)。
BM (Boyer-Moore)：從模式串右端開始比對，結合「壞字符規則」與「好後綴規則」大幅右移 → 實務最快。
Sunday / KMP 改進：利用主串「下一字元」決定位移量，編碼更簡潔。
AC 自動機 (Aho-Corasick)：多模式串同時匹配，構建 Trie + 失敗指標。

Java 內建實作參考

// String.indexOf 底層通常採用優化的暴力匹配或 Two-Way 算法
int idx = text.indexOf(pattern); // 返回首次出現索引，無則 -1

// 正則表達式（較重，適用複雜模式）
java.util.regex.Pattern p = java.util.regex.Pattern.compile(pattern);
java.util.regex.Matcher m = p.matcher(text);
if (m.find()) System.out.println("索引：" + m.start());