萬盛學電腦網

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

JavaScript 數據結構與算法(五):KMP 算法原理解析與完整實現

從 BF 到 KMP:核心優化點

BF 算法失配時模式串固定右移 1 位,導致大量已知匹配信息被浪費。KMP (Knuth-Morris-Pratt) 算法利用模式串內部的前綴-後綴匹配特性,動態計算最大跳躍距離,將時間複雜度從 O(mn) 降至 O(m+n)。

核心概念:部分匹配表

對模式串 P 的每個前綴子串,計算其最長相等前綴後綴長度(不包含整個子串本身)。

以 P = "aaronaac" 為例

索引字符前綴集合後綴集合最長公共長度
0a∅∅0
1a{a}{a}1
2r{a, aa}{r, ar}0
3o{a, aa, aar}{o, ro, aro}0
4n{a, aa, aar, aaro}{n, on, ron, aron}0
5a{a, aa, aar, aaro, aaron}{a, na, ona, rona, arona}1
6a{a, aa, aar, aaro, aaron, aarona}{a, aa, naa, onaa, ronaa, aronaa}2
7c{a, aa, aar, aaro, aaron, aarona, aaronaa}{c, ac, aac, naac, onaac, ronaac, aronaac}0

得到 next 數組(部分匹配值):[0, 1, 0, 0, 0, 1, 2, 0]

跳躍公式推導

當在位置 j 失配(已匹配 j 個字符)時:

移動位數 = 已匹配字符數 - 部分匹配值 = j - next[j-1]

模式串新的比對起點 = j - next[j-1],主串指針 不回退。

KMP 完整實現(兩種風格)

實現一:預計算 next 數組(標準教科書風格)

// 計算 next 數組(部分匹配表)
function buildNext(pattern) {
  var next = [0];
  var j = 0; // 前綴末尾指針
  for (var i = 1; i < pattern.length; i++) {
    while (j > 0 && pattern[i] !== pattern[j]) {
      j = next[j - 1]; // 遞歸回退
    }
    if (pattern[i] === pattern[j]) j++;
    next[i] = j;
  }
  return next;
}

// KMP 主函數
function kmpSearch(text, pattern) {
  if (!pattern.length) return 0;
  var next = buildNext(pattern);
  var j = 0; // 模式串指針
  
  for (var i = 0; i < text.length; i++) {
    while (j > 0 && text[i] !== pattern[j]) {
      j = next[j - 1]; // 關鍵:利用 next 跳躍,i 不動
    }
    if (text[i] === pattern[j]) j++;
    if (j === pattern.length) {
      return i - j + 1; // 匹配成功,返回起始索引
    }
  }
  return -1;
}

實現二:動態計算 next(節省空間,單次遍歷)

function kmpSearchDynamic(text, pattern) {
  var m = pattern.length, n = text.length;
  if (m === 0) return 0;
  
  // 動態構建 next 並同時匹配
  var next = new Array(m);
  next[0] = 0;
  var j = 0;
  
  for (var i = 1; i < m; i++) { // 先構建完整 next
    while (j > 0 && pattern[i] !== pattern[j]) j = next[j - 1];
    if (pattern[i] === pattern[j]) j++;
    next[i] = j;
  }
  
  j = 0;
  for (var i = 0; i < n; i++) { // 匹配階段
    while (j > 0 && text[i] !== pattern[j]) j = next[j - 1];
    if (text[i] === pattern[j]) j++;
    if (j === m) return i - m + 1;
  }
  return -1;
}

圖解匹配過程

BF與KMP對比圖

圖中主串 T、模式串 P,第 6 字符失配時:

  • BF:模式串右移 1 位,主串回退重比
  • KMP:已匹配 ababa (5字符),next[4]=1,右移 5-1=4 位,主串指針不動

JavaScript 專項優化技巧

  1. 字符串訪問優化:str.charAt(i) 比 str[i] 在舊引擎更快,現代引擎已優化一致
  2. 避免屬性訪問:將 pattern.length、text.length 緩存到局部變量
  3. 類型化數組:var next = new Uint16Array(m) 減少內存佔用(適用超長模式串)
  4. 早期退出:if (n < m) return -1;

實戰應用場景

  • 文本編輯器查找/替換:大文件(MB級)毫秒級響應
  • 關鍵詞過濾/敏感詞檢測:多模式串可擴展為 AC 自動機
  • 生物信息學序列比對:DNA/蛋白質序列匹配
  • 前端路由匹配:路由路徑模式匹配(如 /user/:id/post/:pid)

對比總結:BF vs KMP vs BM vs Sunday

算法時間複雜度空間複雜度匹配方向JS實現難度適用場景
BFO(mn)O(1)左→右⭐極短模式串、教學
KMPO(m+n)O(m)左→右⭐⭐⭐通用單模式匹配、流式處理
BMO(m+n) 最好 O(n/m)O(σ)右→左⭐⭐⭐⭐長模式串、字母表大
SundayO(m+n) 最好 O(n/m)O(σ)左→右⭐⭐⭐實際工程常用、比BM簡單

σ 為字符集大小

總結

KMP 算法通過預處理模式串構建 next 數組,實現主串指針零回退,是字符串匹配從「暴力」走向「智能」的關鍵一步。JavaScript 實現時注意緩存長度、優化字符訪問、善用類型化數組。掌握 KMP 不僅能應對面試,更能在文本處理、搜索建議、路由匹配等實際業務中發揮核心作用。

copyright © 萬盛學電腦網 all rights reserved