JavaScript不使用every方法实现高性能多字符串匹配的方案

原实现的时间复杂度为O(k*n)，其中k为关键词数量，n为目标字符串长度。每匹配一个关键词就要完整遍历一次目标字符串，当目标字符串长度极大、关键词数量较多时，性能会线性下降，以下是对应场景的优化方案：

优化方案 #

方案1：完整单词匹配场景（优先选择，实现最简单） #

如果你的匹配规则是匹配完整独立单词（而非子串，比如关键词java不会命中目标串里的javascript），可以先把目标字符串的所有单词存入Set，后续关键词查询时间复杂度降为O(1)，整体复杂度降到O(n + k)，性能提升极明显。
代码示例：

const targetStr = 'you should code in javascript'
// 仅需遍历1次目标字符串生成词集合
const targetWordSet = new Set(targetStr.split(' '))
// 每个关键词查询都是O(1)
const result = 'javascript code'.split(' ').every(val => targetWordSet.has(val))

方案2：子串匹配场景（多关键词+大字符串最优） #

如果需要匹配任意子串（比如关键词java要命中javascript），可以使用多模式匹配经典算法Aho-Corasick（AC自动机），仅需遍历1次目标字符串就能完成所有关键词的匹配，整体时间复杂度为O(n + k + m)，其中m为匹配结果数量，远优于原实现的线性遍历。
简化版实现代码示例：

// AC自动机节点类
class ACNode {
  constructor() {
    this.children = new Map()
    this.fail = null
    // 存储当前节点对应的结束关键词
    this.pattern = null
  }
}

// 构建AC自动机
function buildAC(patterns) {
  const root = new ACNode()
  // 插入所有关键词
  for (const pattern of patterns) {
    let node = root
    for (const char of pattern) {
      if (!node.children.has(char)) {
        node.children.set(char, new ACNode())
      }
      node = node.children.get(char)
    }
    node.pattern = pattern
  }
  // 构建失败指针（BFS）
  const queue = [root]
  root.fail = null
  while (queue.length) {
    const currNode = queue.shift()
    for (const [char, childNode] of currNode.children) {
      let failNode = currNode.fail
      while (failNode && !failNode.children.has(char)) {
        failNode = failNode.fail
      }
      childNode.fail = failNode ? failNode.children.get(char) : root
      queue.push(childNode)
    }
  }
  return root
}

// 匹配所有关键词是否都存在
function matchAllPatterns(root, targetStr, patterns) {
  const matched = new Set()
  let currNode = root
  for (const char of targetStr) {
    while (currNode && !currNode.children.has(char)) {
      currNode = currNode.fail
    }
    currNode = currNode ? currNode.children.get(char) : root
    // 收集所有匹配的关键词，全匹配直接提前返回
    let temp = currNode
    while (temp) {
      if (temp.pattern) {
        matched.add(temp.pattern)
        if (matched.size === patterns.length) return true
      }
      temp = temp.fail
    }
  }
  return matched.size === patterns.length
}

// 使用示例
const patterns = 'javascript code'.split(' ')
const acRoot = buildAC(patterns)
const targetStr = 'you should code in javascript'
const result = matchAllPatterns(acRoot, targetStr, patterns)

如果关键词是固定重复使用的，可以提前构建AC自动机缓存，不用每次匹配都重新生成，性能会进一步提升。

方案3：少量关键词场景 #

如果你的关键词数量极少（小于3个），原实现的性能差异可以忽略，不需要额外修改。

内容的提问来源于stack exchange，提问作者htoniv