暴力模式匹配是字串搜尋最直觀的演算法:從目標字串的第一個字元開始,逐一與模式字串比對;失敗時目標字串往後移一位,模式字串回到開頭,重複比對,直到找到匹配或目標字串結束。雖然時間複雜度為 O(m×n),但在短字串或教學場合仍具參考價值。
假設目標字串 T = "ABCDABCE",模式字串 P = "ABCE":
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) |
| 實作難度 | 低 | 中/高 |
| 適用場景 | 短字串、教學、原型驗證 | 長文本、高頻搜尋、生產系統 |
實務開發中,直接使用 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,僅在嵌入式環境、教學示範或特殊約束下考慮手寫實作。