前端男孩

# 字符串匹配算法

字符串匹配算法（String-searching algorithm）是一种试图在较长字符串（文本）中找到是否包含一个或多个字符串（模式）或者出现位置的搜索算法。

# 朴素字符串匹配算法

朴素字符串匹配算法（Brute Force，简称 BF 算法）的核心思想是通过在文本中遍历每个可能的位置，逐个比较模式和文本对应的字符，以找到匹配的子串。

以下是 BF 算法的代码实现：

该代码使用一个指针 i 跟踪文本，一个指针 j 跟踪模式，在 n - m + 1 个子串中逐个比较指针对应的字符，直到找到一个不匹配的字符或模式匹配结束为止。

function bruteForce(text, pattern) {
  const n = text.length;
  const m = pattern.length;

  for (let i = 0; i < n - m + 1; i++) {
    let j = 0;
    while (j < m) {
      if (text[i + j] !== pattern[j]) break;
      j++;
    }

    if (j === m) return i;
  }

  return -1;
}

BF 算法还有一种显示回退的实现，代码实现如下：

function bruteForce2(text, pattern) {
  const n = text.length;
  const m = pattern.length;
  let i = 0;
  let j = 0;

  while (i < n && j < m) {
    if (text[i] === pattern[j]) {
      i++; j++;
    } else {
      i = i - j + 1;
      j = 0;
    }
  }

  return j === m ? i - j : -1;
}

该代码同样使用一个指针 i 跟踪文本，一个指针 j 跟踪模式。如果两个指针指向的字符匹配时，我们将比较文本和模式的下一个字符；否则重新将 i 指向本次匹配的开始位置的下一个字符，将 j 指向模式的开头。

BF 算法的优点在于直观简单，而缺点在于执行效率低。在最坏情况下（两个字符串除了最后一个字符其他都匹配），BF 算法需要在长度为 n 的文本中比较 m 次模式中的字符，所以最坏时间复杂度为 O(nm)。

# Knuth-Morris-Pratt 算法

# Boyer-Moore 算法

# Rabin-Karp算法

# 参考

更新时间: 6/19/2022, 8:15:37 PM

← 简介 →