DIV CSS 佈局教程網

JavaScript 數據結構與算法(四):字符串與 BF 暴力匹配算法
編輯:JavaScript綜合知識     

在數據結構的學習路徑上,字符串(也稱「串」)常被視為一種特殊的線性表。本文是這個系列的第四篇,重點放在串的抽象定義,以及最直觀易懂的模式匹配算法——BF(Brute Force,暴力匹配,又稱樸素匹配或蠻力算法)。

一、什麼是串

串是由零個或多個字符組成的有限序列。它的邏輯結構與線性表高度相似:元素按先後順序排成一條線,每個位置對應唯一元素。真正的差別在於操作對象——串的元素被限定為字符,因此圍繞它展開的操作也完全不同。

線性表更關注單個元素的增刪改查(CRUD),串則更關注定位與替換:某個子串第一次出現在哪裡、如何把一段內容替換掉、如何截取片段。各高級語言對串的基本操作命名不同,但本質相通。以 JavaScript 為例,查找用 indexOf,去空白用 trim,大小寫轉換用 toLowerCase / toUpperCase。

二、經典的模式匹配算法

字符串匹配有三個繞不開的名字:BF、BM、KMP。它們解決的是同一個問題——在主串中找出模式串第一次出現的位置——差別在於「失配之後怎麼走」。

BF 算法的基本思想

從主串 s 的第一個字符開始,與模式串 t 的第一個字符比較。若相等,就繼續逐個向後比較;若不相等,主串指針回到起點的下一個位置,模式串指針回到首位,重新開始比較。

如此反覆,直到模式串 t 的每個字符都與主串 s 中某段連續字符依次相等,則匹配成功,此時 t 的首字符在 s 中的下標即為結果;若一直走到主串末尾仍未成功,則匹配失敗。

可以看到,BF 的思路非常「樸素」:主串的每個位置都試一次,試到為止。它的實現恰好對應了 JavaScript 中 indexOf 的內涵。

三、最直白的實現

以主串 BBC ABB ABCF、子串 ABC 為例:

var sourceStr = "BBC ABB ABCF";
var searchStr = "ABC";

function BF_Ordinary(sourceStr, searchStr) {
  var sourceLength = sourceStr.length;
  var searchLength = searchStr.length;
  var padding = sourceLength - searchLength;

  // 外層最多只需要比較 padding + 1 次
  for (var i = 0; i <= padding; i++) {
    // 首字符相等才進入內層逐位比對
    if (sourceStr.charAt(i) == searchStr.charAt(0)) {
      var complete = searchLength;
      for (var j = 0; j < searchLength; j++) {
        if (sourceStr.charAt(i + j) == searchStr.charAt(j)) {
          --complete;
          if (!complete) return i; // 全部匹配完成
        }
      }
    }
  }
  return -1;
}

這段代碼有三個容易寫錯的地方:

  • 外層循環上界是 sourceLength - searchLength,因為主串剩餘長度小於子串時不可能再匹配成功,繼續循環是浪費。
  • 內層取值時主串下標必須疊加偏移量 i + j,而不是單獨用 j。
  • 用一個計數變量 complete 判斷是否全部匹配。在 BBC ABB ABCF 的例子中,第二段的 ABB 首字符相同但後續不同,必須能被正確跳過。

四、優化寫法一:把判斷條件反過來

與其統計「匹配了多少個」,不如只關注「有沒有不匹配」。一旦發現某一位不同,立刻判定本輪失敗並跳出內層。

function BF_Optimize(sourceStr, searchStr) {
  var mainLength = sourceStr.length;
  var searchLength = searchStr.length;
  var padding = mainLength - searchLength;

  for (var offset = 0; offset <= padding; offset++) {
    var match = true;
    for (var i = 0; i < searchLength; i++) {
      // 只要出現一次不相等就結束本輪
      if (searchStr.charAt(i) !== sourceStr.charAt(offset + i)) {
        match = false;
        break;
      }
    }
    if (match) return offset;
  }
  return -1;
}

內層循環完整跑完而 match 未被改寫,即說明這一輪是完全匹配。這種「取反短路」的寫法通常比正統計數更易讀,也更符合多數語言的習慣。

五、優化寫法二:單循環 + 雙指針

仔細觀察會發現規律:外層每次只把主串起點後移一位,內層每次都從模式串頭部重新開始。既然如此,其實可以只用一個 while 循環,靠兩個下標指針的移動來表達同樣的過程。

function BF_Optimize_2(sourceStr, searchStr) {
  var i = 0, j = 0;

  while (i < sourceStr.length) {
    if (sourceStr.charAt(i) == searchStr.charAt(j)) {
      i++; j++;              // 相等則同時前進
    } else {
      i = i - j + 1;         // 主串回到本輪起點的下一個位置
      j = 0;                 // 模式串回到首位
    }

    if (j == searchStr.length) {
      return i - j;          // 模式串走完,i - j 即起始下標
    }
  }
  return -1;
}

這裡的關鍵是回退公式 i = i - j + 1。因為在內層推進過程中 i 已經被疊加了 j 次,要退回「本輪起點 + 1」,就必須先減去 j 再加一。很多實現出錯都出在這一步。

六、優化寫法三:遞歸版本

function BF_Recursive(sourceStr, searchStr, offset) {
  var mainLength = sourceStr.length;
  var searchLength = searchStr.length;

  // 剩餘長度不足以容納模式串,直接失敗
  if (searchLength > mainLength - offset) return -1;

  offset = offset || 0;
  for (var i = 0; i < searchLength; i++) {
    if (searchStr.charAt(i) !== sourceStr.charAt(offset + i)) {
      return BF_Recursive(sourceStr, searchStr, offset + 1);
    }
  }
  return offset;
}

遞歸版本的語義最貼近算法定義本身:當前位置不匹配,就把起點右移一位再問一次自己。代價是額外的函數調用開銷,在字符串很長時需要留意棧深度。

七、複雜度與局限

BF 的最壞時間複雜度為 O(mn)(m 為模式串長度,n 為主串長度),空間複雜度 O(1)。它的致命弱點在於:一旦某一位失配,主串指針必須整體回退,此前已經比較過的字符信息全部被丟棄、重新比較。

當主串中存在大量重複前綴(例如 aaaaaaaab 中查找 aaab)時,這種浪費會被放大得非常明顯。BF 屬於前綴匹配算法,如何「不回退地利用已匹配信息」,正是 KMP 與 BM 要解決的問題,後續文章會接著展開。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved