字符串是字符的有限序列,邏輯結構類似線性表,但操作焦點在於子串查找、替換、匹配。JavaScript 原生提供 indexOf、search、match 等方法,底層即為模式匹配算法的實現。本文聚焦經典的 BF (Brute Force) 暴力匹配算法 及其優化演進。
從主串 S 第 0 位開始,與模式串 T 第 0 位逐字符比對:
直到模式串完全匹配(成功)或主串遍歷結束(失敗)。時間複雜度 O(m×n),m、n 分別為主串與模式串長度。

function BF_Ordinary(sourceStr, searchStr) {
var sourceLen = sourceStr.length;
var searchLen = searchStr.length;
var padding = sourceLen - searchLen; // 最大嘗試次數
for (var i = 0; i <= padding; i++) {
// 首字符匹配才進入內層
if (sourceStr.charAt(i) === searchStr.charAt(0)) {
var complete = searchLen;
for (var j = 0; j < searchLen; j++) {
if (sourceStr.charAt(i + j) === searchStr.charAt(j)) {
complete--;
if (complete === 0) return i; // 完全匹配
} else {
break; // 中途失配,跳出內層
}
}
}
}
return -1;
}
sourceLen - searchLen,因為剩餘長度不足模式串時無需嘗試i + j,體現「主串位置疊加」complete 計數器避免額外標誌變量只關注「不相等」即可提前跳出,匹配成功時 match 保持 true。
function BF_Optimize(sourceStr, searchStr) {
var mainLen = sourceStr.length;
var searchLen = searchStr.length;
var padding = mainLen - searchLen;
for (var offset = 0; offset <= padding; offset++) {
var match = true;
for (var i = 0; i < searchLen; i++) {
if (searchStr.charAt(i) !== sourceStr.charAt(offset + i)) {
match = false;
break;
}
}
if (match) return offset;
}
return -1;
}
觀察規律:主串指針 i 單調遞增,模式串指針 j 匹配時同步遞增,失配時 i 回退至 i - j + 1,j 歸零。消除了嵌套循環,邏輯更緊湊。
function BF_Optimize_2(sourceStr, searchStr) {
var i = 0, j = 0;
var sourceLen = sourceStr.length;
var searchLen = searchStr.length;
while (i < sourceLen && j < searchLen) {
if (sourceStr.charAt(i) === searchStr.charAt(j)) {
i++; j++;
} else {
i = i - j + 1; // 回退到上次匹配起始位置的下一個
j = 0;
}
}
return (j === searchLen) ? i - j : -1;
}
| 版本 | 結構 | 可讀性 | 性能 | 適用場景 |
|---|---|---|---|---|
| 基礎版 | for + for | ⭐⭐⭐ | 基準 | 教學演示 |
| 優化一 | for + for (取反) | ⭐⭐⭐⭐ | +10~15% | 一般生產 |
| 優化二 | while 雙指針 | ⭐⭐⭐⭐ | +20~30% | 高性能要求 |
| 遞歸版 | 遞歸函數 | ⭐⭐ | 較差(棧開銷) | 算法練習 |
V8 引擎中 String.prototype.indexOf 採用 Two-Way Algorithm(雙向算法,結合 BF 與 KMP 優點),對短模式串仍使用優化 BF,長模式串切換至 KMP/BM。理解 BF 算法是掌握更高級算法(KMP、BM、Sunday)的基石。
28. Find the Index of the First Occurrence in a String 驗證實現indexOf、search、match 在極長字符串(10萬+字符)下的性能差異replaceAll 核心邏輯:基於 BF 找到所有匹配位置後批量替換BF 算法雖屬「暴力」,但思想直觀、實現簡單,是字符串匹配的入門基石。通過「取反邏輯」與「雙指針單循環」兩輪優化,可顯著提升性能並簡化代碼結構。掌握 BF 為後續學習 KMP(利用部分匹配表跳過無效比對)、BM(後綴匹配+壞字符規則)等高級算法奠定堅實基礎。