DIV CSS 佈局教程網

JavaScript 資料結構與演算法:KMP 字串搜尋
編輯:關於JavaScript     

KMP 是經典的字串搜尋演算法,重點在於利用已匹配資訊減少回溯。與暴力搜尋相比,它能避免主串指標大幅倒退,提高效率。

部分匹配表

KMP 的核心是 next 陣列。它記錄模式串每個位置之前,前綴與後綴相同的最長長度。當比對失敗時,可根據這個表移動模式串,而不必從頭開始。

建立 next 陣列

function buildNext(pattern) {
  const chars = Array.from(pattern);
  const next = [0];
  let j = 0;

  for (let i = 1; i !== chars.length; i++) {
    while (j > 0 && chars[i] !== chars[j]) {
      j = next[j - 1];
    }
    if (chars[i] === chars[j]) {
      j++;
    }
    next[i] = j;
  }
  return next;
}

搜尋流程

比對時,若目前字元相同,主串與模式串指標同時前進;若不同,則依 next 陣列調整模式串指標。當模式串指標等於模式串長度,即代表找到匹配位置。

KMP 的時間複雜度通常為線性,適合作為長文字搜尋與演算法學習的基礎。

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