Java 模式匹配之暴力匹配算法實現

暴力匹配算法（Brute Force）原理

暴力匹配是最直觀的字符串查找算法：從目標串第一個字符開始，依次與模式串逐字符比較；匹配失敗時，目標串回溯到下一個起始位置，模式串重置到首字符，繼續比較。雖然時間複雜度為 O(m×n)，但實現簡單，適用於短文本或教學場景。

標準實現代碼

package javay.util;

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

    /**
     * 暴力匹配查找模式串在目標串中首次出現的位置
     * @param target 目標串
     * @param pattern 模式串
     * @return 首次匹配位置，未找到返回 -1
     */
    public static int patternMatch(String target, String pattern) {
        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++;
                idxPtn = 0;
                idxTgt = index;
            }
        }

        return (idxPtn == patternLength) ? index : -1;
    }
}

JDK 風格實現參考

以下代碼參考自 JDK String.indexOf() 的實現邏輯，採用優化的字符數組操作：

static int indexOf(char[] source, char[] target) {
    char first = target[0];
    int max = source.length - target.length;

    for (int i = 0; i <= max; i++) {
        // 快速跳過非首字符
        if (source[i] != first) {
            while (++i <= max && source[i] != first);
        }
        // 找到首字符，驗證後續字符
        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;
}

算法對比與選擇建議

總結

暴力匹配雖非最高效，但邏輯清晰、無需預處理，是理解字符串匹配的基礎。生產環境中，Java 內置的 String.indexOf()、Pattern/Matcher 或第三方庫（如 Apache Commons Lang StringUtils）已高度優化，建議直接使用。