algorithm - 用 搜索字符串。通配符

Question

我有一个包含很多字符串的数组，我想在其中搜索一个模式。 这个模式可以有一些“。”匹配(每个)1 个字符(任意)的通配符。

例如:

myset = {"bar", "foo", "cya", "test"}

find(myset, "f.o") -> returns true (matches with "foo") 
find(myset, "foo.") -> returns false 
find(myset, ".e.t") -> returns true (matches with "test")
find(myset, "cya") -> returns true (matches with "cya")

我试图找到一种快速实现该算法的方法，因为 myset 实际上是一个非常大的数组，但我的想法都没有令人满意的复杂度(例如 O(size_of(myset) * 长度(图案)))

编辑:

myset 是一个巨大的数组，里面的字并不大。 我可以做一个缓慢的预处理。但是我会有很多 find() 查询，所以 find() 我希望 find() 尽可能快。

Answer 1

您可以为集合中所有可能单词的语料库构建一个后缀树 ( see this link ) 使用此数据结构，您的复杂性将包括 O(n) 的一次性成本来构建树，其中 n 是所有单词长度的总和。

构建树后，查找字符串是否匹配应该只需要 O(n)，其中 n 是字符串的长度。