string - 查找给定字符串匹配的模式列表中的哪一个

Question

我有一组固定的未知模式字符串，它们使用通配符*和?（?=一个字符，*=零个或多个字符）。例如：

• "abcd?"
• "dogcat*"
• "*car"
• "hello*world"

我想从这些模式中生成一些数据结构，它有一个名为findPattern. 该方法接受一个保证最多匹配一个模式的字符串，并返回字符串匹配的模式（如果有的话）。

在上面的例子中：

• findPattern("abcde")返回"abcd?"
• findPattern("hellocar")返回"*car"
• findPattern("edbca")返回null

"dogcatfrogcar"保证不会将诸如此类的字符串作为此方法的输入。

构建数据结构可能很慢，因为模式集只给出一次。该函数将被同一模式集上的许多字符串调用，因此它需要高效。

我如何实现这一目标？

PS我是编程语言不可知论者

Answer 1

Aho-Corasic 算法旨在找到文本中的多个模式。幸运的是，可以使用 '?' 通配符（单个符号），以及“如果通配符的数量以常数为界，则可以在线性时间内匹配带有通配符的模式”

Answer 2

我们可以用正则表达式替换每个模式，并尝试解决更普遍的问题。

在那种情况下，我发现了一些有趣的方法：

1. RE2 库，它允许同时匹配多个正则表达式（只要它们没有反向引用，这里就是这种情况） - 请参阅此答案。
2. Lex和类似 Lex 的词法分析器 - 请参阅此答案。