0

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

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

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

在上面的例子中：

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

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

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

我如何实现这一目标？

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

4

2 回答 2

1

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

于 2013-07-15T05:03:20.650 回答
0

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

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

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