介绍

在计算机科学中，Knuth-Morris-Pratt 字符串查找算法（简称为 KMP 算法）可在一个字符串 S 内查找一个词 W 的出现位置。一个词在不匹配时本身就包含足够的信息来确定下一个匹配可能的开始位置，此算法利用这一特性以避免重新检查先前配对的字符。

实现

JavaScript

// Implementing KMP Search Algorithm to search all the instances of pattern in
// given text
// Reference Book: Introduction to Algorithms, CLRS

// Explanation: https://www.topcoder.com/community/competitive-programming/tutorials/introduction-to-string-searching-algorithms/

const computeLPS = (pattern) => {
  const lps = Array(pattern.length)
  lps[0] = 0
  for (let i = 1; i < pattern.length; i++) {
    let matched = lps[i - 1]
    while (matched > 0 && pattern[i] !== pattern[matched]) {
      matched = lps[matched - 1]
    }
    if (pattern[i] === pattern[matched]) {
      matched++
    }
    lps[i] = matched
  }
  return lps
}

/**
 * Returns all indices where pattern starts in text
 * @param {*} text a big text in which pattern string is to find
 * @param {*} pattern the string to find
 */
const KMPSearch = (text, pattern) => {
  if (!pattern || !text) {
    return [] // no results
  }

  // lps[i] = length of proper prefix of pattern[0]...pattern[i-1]
  //          which is also proper suffix of it
  const lps = computeLPS(pattern)
  const result = []

  let matched = 0
  for (let i = 0; i < text.length; i++) {
    while (matched > 0 && text[i] !== pattern[matched]) {
      matched = lps[matched - 1]
    }
    if (text[i] === pattern[matched]) {
      matched++
    }
    if (matched === pattern.length) {
      result.push(i - pattern.length + 1)
      matched = lps[matched - 1]
    }
  }

  return result
}

参考

• Knuth–Morris–Pratt algorithm - Wikiwand (opens new window)
• KMP 算法 - Wikiwand (opens new window)
• 字符串匹配的 KMP 算法 - 阮一峰的网络日志 (opens new window)