萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

Java 模式匹配:暴力演算法 (Brute Force) 深度解析與實作

什麼是暴力模式匹配?

暴力模式匹配是字串搜尋最直觀的演算法:從目標字串的第一個字元開始,逐一與模式字串比對;失敗時目標字串往後移一位,模式字串回到開頭,重複比對,直到找到匹配或目標字串結束。雖然時間複雜度為 O(m×n),但在短字串或教學場合仍具參考價值。

核心邏輯圖解

假設目標字串 T = "ABCDABCE",模式字串 P = "ABCE":

  1. T[0..3] 與 P[0..3] 比對:A=B? 不,移動
  2. T[1..4] 與 P[0..3] 比對:B=A? 不,移動
  3. ...
  4. T[4..7] 與 P[0..3] 完全匹配,回傳索引 4

標準實作程式碼

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) {
            throw new IllegalArgumentException("字串不得為 null");
        }
        
        int targetLength = target.length();
        int patternLength = pattern.length();
        
        // 邊界條件:模式比目標長,不可能匹配
        if (patternLength > targetLength) {
            return -1;
        }
        
        int idxTgt = 0; // 目標字串當前比對位置
        int idxPtn = 0; // 模式字串當前比對位置
        int startIndex = 0; // 當前嘗試匹配的起始位置
        
        while (idxTgt < targetLength && idxPtn < patternLength) {
            if (target.charAt(idxTgt) == pattern.charAt(idxPtn)) {
                // 字元匹配,雙雙前進
                idxTgt++;
                idxPtn++;
            } else {
                // 失敗:目標字串回到下一個起始位置,模式字串歸零
                startIndex++;
                idxTgt = startIndex;
                idxPtn = 0;
            }
        }
        
        // 判斷是否匹配成功
        return (idxPtn == patternLength) ? startIndex : -1;
    }
}

效能分析與優化方向

指標暴力演算法KMP / Boyer-Moore
時間複雜度O(m×n)O(m+n)
空間複雜度O(1)O(m)
實作難度低中/高
適用場景短字串、教學、原型驗證長文本、高頻搜尋、生產系統

Java 內建的高效替代方案

實務開發中,直接使用 JDK 內建方法即可,底層已優化(Java 9+ 使用雙向掃描演算法):

String text = "ABCDABCE";
String pattern = "ABCE";

// 回傳首次出現索引,找不到回傳 -1
int index = text.indexOf(pattern); 

// 正則表達式需求
import java.util.regex.*;
Pattern p = Pattern.compile(Pattern.quote(pattern)); // 字面匹配,避免特殊字元
Matcher m = p.matcher(text);
if (m.find()) {
    System.out.println("找到於索引:" + m.start());
}

字元陣列版本(效能微調)

原文提供的 indexOf(char[], char[]) 版本針對字元陣列優化,避免建立字串物件,適合極度效能敏感場景:

static int indexOf(char[] source, char[] target) {
    if (source == null || target == null || target.length == 0) return -1;
    if (target.length > source.length) return -1;
    
    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;
}

總結

暴力匹配雖非生產環境首選,但理解其「雙指針回溯」機制是掌握 KMP、Sunday 等進階演算法的基石。實務上請優先使用 String.indexOf() 或 java.util.regex,僅在嵌入式環境、教學示範或特殊約束下考慮手寫實作。

copyright © 萬盛學電腦網 all rights reserved