如何在JavaScript中检查字符串是否包含子字符串

在JavaScript中，有多种方法可以检查一个字符串是否包含另一子字符串。最常见的方法是使用String.prototype.includes()，它可以简单明了地完成这一任务。然而，如果你更关心最坏情况下的时间复杂度，KMP（Knuth–Morris–Pratt）算法可能是一个更合理的选择。

为什么选择KMP算法？

KMP算法在最坏情况下搜索一个长度为m的子字符串在一个长度为n的字符串中的时间复杂度为O(n+m)，相比之下，朴素的字符串匹配算法在最坏情况下的时间复杂度为O(n⋅m)。因此，如果你要处理的是一个具有很长字符串或子字符串的情况，KMP算法将显得更加高效。

KMP算法的基本原理

KMP算法通过预处理模式串，形成一个部分匹配表（Longest Suffix Prefix, LSP表），来避免在匹配过程中不必要的重复检查。LSP表记录了子字符串每个前缀的最长前缀后缀的信息，从而指导搜索过程中需要跳过多少字符。

实现KMP算法的JavaScript代码

以下是由 Project Nayuki 提供的一个 JavaScript 实现示例，来自 nayuki.io：

// 使用Knuth-Morris-Pratt字符串匹配算法在给定的文本字符串中搜索给定的模式字符串。
// 如果找到模式字符串，则返回匹配开始处的索引。否则返回-1。
function kmpSearch(pattern, text) {
  if (pattern.length == 0) return 0 // 立即匹配

  // 计算最长前缀后缀表
  var lsp = [0] // 基本情况
  for (var i = 1; i < pattern.length; i++) {
    var j = lsp[i - 1] // 假设我们在延长之前的LSP
    while (j > 0 && pattern[i] !== pattern[j]) j = lsp[j - 1]
    if (pattern[i] === pattern[j]) j++
    lsp.push(j)
  }

  // 遍历文本字符串
  var j = 0 // 模式中匹配的字符数
  for (var i = 0; i < text.length; i++) {
    while (j > 0 && text[i] != pattern[j]) j = lsp[j - 1] // 回退模式
    if (text[i] == pattern[j]) {
      j++ // 下一个字符匹配，增加位置
      if (j == pattern.length) return i - (j - 1)
    }
  }
  return -1 // 没找到
}

console.log(kmpSearch('ays', 'haystack') != -1) // 输出：true
console.log(kmpSearch('asdf', 'haystack') != -1) // 输出：false

结论

在日常的JavaScript开发中，处理简单的字符串包含检查时，includes()方法足以应付。然而，在复杂或大型字符串匹配的场景中，KMP算法提供了一种高效的解决方案，值得深入掌握和使用。