Java 模式匹配：暴力匹配演算法完整實作與解析

字串模式匹配是計算機科學的經典問題。**暴力匹配演算法** 是最直觀、最基礎的解法，雖然時間複雜度較高（O(m×n)），但理解它是學習 KMP、BM 等高效演算法的基石。本文提供完整 Java 實作、執行流程圖解與優化方向。

演算法核心邏輯

基本思想：將模式串與目標串逐字元比對。匹配成功則雙方後移；失敗時，目標串回溯到「下一個起始位置」，模式串重置到開頭。

關鍵變數

• idxTgt：目標串當前比對位置
• idxPtn：模式串當前比對位置
• index：當前嘗試匹配的起始位置（index = idxTgt - idxPtn）

完整 Java 實作（標準版）

package javay.util;

/**
 * 暴力模式匹配演算法
 */
public class PMBF {

    /**
     * 暴力匹配
     * @param target 目標串（文本）
     * @param pattern 模式串（模式）
     * @return 首次匹配的起始索引，失敗回傳 -1
     */
    public static int patternMatch(String target, String pattern) {
        if (target == null || pattern == null) return -1;
        if (pattern.isEmpty()) return 0; // 空模式串匹配任意位置

        int targetLength = target.length();
        int patternLength = pattern.length();

        int idxTgt = 0; // 目標串索引
        int idxPtn = 0; // 模式串索引
        int index = 0;  // 當前匹配起始位置

        while (idxTgt < targetLength && idxPtn < patternLength) {
            if (target.charAt(idxTgt) == pattern.charAt(idxPtn)) {
                // 字元匹配，雙方後移
                idxTgt++;
                idxPtn++;
            } else {
                // 失敗：目標串回溯到下一個起始位置，模式串重置
                index++;
                idxTgt = index;
                idxPtn = 0;
            }
        }

        // 判斷是否匹配成功
        return (idxPtn == patternLength) ? index : -1;
    }

    // 測試主程式
    public static void main(String[] args) {
        String text = "ABABCABABABCDABC";
        String pattern = "ABABCD";
        int pos = patternMatch(text, pattern);
        System.out.println("文本: " + text);
        System.out.println("模式: " + pattern);
        System.out.println("匹配位置: " + pos); // 輸出: 7
    }
}

執行流程圖解（以 "ABABC" 匹配 "ABABCD" 為例）

目標串: A B A B C
模式串: A B A B C D
        ↑           起始 index=0
        匹配 A==A, B==B, A==A, B==B, C==C
        模式串結束? 否 (還有 D)
        目標串結束? 是
        → 返回 -1 (匹配失敗)

替代實作：陣列版（參考 JDK String.indexOf 風格）

/**
 * 字元陣列版暴力匹配（參考 JDK 實作風格）
 * @param source 來源字元陣列
 * @param target 目標字元陣列
 * @return 首次出現索引，失敗 -1
 */
static int indexOf(char[] source, char[] target) {
    if (source == null || target == null) return -1;
    if (target.length == 0) return 0;
    if (source.length < target.length) return -1;

    char first = target[0];
    int max = source.length - target.length;

    for (int i = 0; i <= max; i++) {
        // 1. 快速定位首字元
        if (source[i] != first) {
            while (++i <= max && source[i] != first);
        }
        // 2. 首字元匹配後，檢查剩餘字元
        if (i <= max) {
            int j = i + 1;
            int end = j + target.length - 1;
            for (int k = 1; j < end && source[j] == target[k]; j++, k++);
            if (j == end) return i; // 全部匹配
        }
    }
    return -1;
}

複雜度分析與優化方向

常見面試延伸問題

1. 為什麼暴力匹配效率低？ 失敗時目標串指針回溯，導致重複比對已檢查過的字元。
2. 如何避免回溯？ KMP 演算法預處理模式串產生 next[]（部分匹配表），失敗時模式串根據 next[] 智慧滑動，目標串指針不回溯。
3. Java String.indexOf() 內部用什麼演算法？ JDK 8+ 針對不同長度採用混合策略：短模式用優化暴力匹配，長模式用 Two-Way Algorithm (類似 KMP)。

總結

暴力匹配雖非生產環境首選，但其直觀的雙指針邏輯是理解所有進階字串匹配演算法的基礎。掌握「匹配成功雙前進、失敗目標回溯模式歸零」的核心模式，能幫助你快速理解 KMP 的 next[] 含義、BM 的壞字元/好後綴規則，以及 Sunday 演算法的優化思路。