萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 數據結構與算法(四):字符串模式匹配——BF 暴力算法與優化

字符串與模式匹配基礎

字符串是字符的有限序列,邏輯結構類似線性表,但操作焦點在於子串查找、替換、匹配。JavaScript 原生提供 indexOf、search、match 等方法,底層即為模式匹配算法的實現。本文聚焦經典的 BF (Brute Force) 暴力匹配算法 及其優化演進。

BF 算法核心思想

從主串 S 第 0 位開始,與模式串 T 第 0 位逐字符比對:

  • 相等 → 兩串同步後移繼續比對
  • 不等 → 主串回溯至上次匹配起始位置 + 1,模式串重置至 0 位

直到模式串完全匹配(成功)或主串遍歷結束(失敗)。時間複雜度 O(m×n),m、n 分別為主串與模式串長度。

BF算法示意圖

基礎實現:雙重循環版

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;
}

關鍵點解析

  1. 外層循環上限:sourceLen - searchLen,因為剩餘長度不足模式串時無需嘗試
  2. 主串索引計算:內層使用 i + j,體現「主串位置疊加」
  3. 完整匹配標記: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%高性能要求
遞歸版遞歸函數⭐⭐較差(棧開銷)算法練習

JS 原生方法底層關聯

V8 引擎中 String.prototype.indexOf 採用 Two-Way Algorithm(雙向算法,結合 BF 與 KMP 優點),對短模式串仍使用優化 BF,長模式串切換至 KMP/BM。理解 BF 算法是掌握更高級算法(KMP、BM、Sunday)的基石。

實戰練習建議

  1. 在 LeetCode 刷題 28. Find the Index of the First Occurrence in a String 驗證實現
  2. 對比 indexOf、search、match 在極長字符串(10萬+字符)下的性能差異
  3. 嘗試實現 replaceAll 核心邏輯:基於 BF 找到所有匹配位置後批量替換

總結

BF 算法雖屬「暴力」,但思想直觀、實現簡單,是字符串匹配的入門基石。通過「取反邏輯」與「雙指針單循環」兩輪優化,可顯著提升性能並簡化代碼結構。掌握 BF 為後續學習 KMP(利用部分匹配表跳過無效比對)、BM(後綴匹配+壞字符規則)等高級算法奠定堅實基礎。

copyright © 萬盛學電腦網 all rights reserved