更快的模式匹配

Question

我需要编写一个模式匹配器，它将打印出可能匹配的所有组合，并且这些模式可以是彼此的子模式，例如模式 eee 是 eeeff 的子模式。

Input: weeeffeeef
Patterns: weee, eee, eeeff, f, w

如您所见，有多个有效的匹配序列，例如

• weee，eee，f，f，eee，f
• w、eee、f、f、eee、f
• w、eeeff、eee、f

等等。有没有一种方法可以在不花费大量时间的情况下找到所有这些模式？

顺便说一句，没有“正确”的顺序。短模式与长模式一样有效，即这不是压缩算法。我只需要所有序列。

Answer 1

基本算法会用到回溯：

function solve(input, patterns, curr_sequence) {
  if (input.is_empty):
    yield curr_sequence
  else
    foreach pattern in patterns:
      if (input.starts_with(pattern)):
        yield* solve(input.slice(pattern.length), patterns, curr_sequence.concat([pattern]))
}

对于简单的输入来说，这可能已经足够快了。如果您需要针对巨大的输入字符串、大量的模式和巨大的模式进行优化，其中模式匹配稀疏（以便生成的序列的绝对数量不会主导运行时间），我会：

• 不要每次都对输入字符串进行切片，因为这可能涉及复制（取决于字符串实现），而是仅传递

  curr_index

  ，然后使用

  input.matches_at(pattern, curr_index)

  而不是

  starts_with

• 不要在每次递归调用时通过串联（涉及复制）创建新的

  curr_sequence

  数组，而是使用可变数组，并仅在字符串末尾成功匹配后实际

  yield

  时才复制它。或者，使用带有

  O(1)

  前缀的链表并在末尾反转它，使用反向列表而不是数组，以便您可以从共享开始中受益，或者使用列表并反向运行算法，以便您可以受益来自分享尾巴。如果您期望获得大量结果序列，共享尤其有帮助。
• 不要重复搜索相同模式的相同后缀，只是使用不同的

  curr_sequence

  ，而是使用 动态规划
• 或者，不要在字符串中的同一位置重复使用

  matches_at

  ，使用相同的模式，而是记住匹配项或简单地预先计算哪些模式与字符串中的位置匹配
• 要计算哪些模式与字符串中的位置匹配，请构建一个 后缀树