使用通配符和不匹配项高效地搜索前缀

Question

给定一个字符串str和一个可变长度前缀列表p，我想找到在str开头找到的所有可能的前缀，允许k不匹配和str中的通配符（点字符）。在

我只想在字符串的开头搜索，并且需要高效地搜索len(p) <= 1000; k <= 5和数百万strs

例如：

str = 'abc.efghijklmnop'
p = ['abc', 'xxx', 'xbc', 'abcxx', 'abcxxx']
k = 1

result = ['abc', 'xbc', 'abcxx'] #but not 'xxx', 'abcxxx'

是否有一个有效的算法来实现这一点，理想情况下已经有了python实现？在

我目前的想法是逐个字符遍历str，并对每个前缀的不匹配计数进行实时统计。在

在每一步，我都会计算一个新的候选列表，即没有太多不匹配的前缀列表。在

如果我到达前缀的末尾，它就会被添加到返回的列表中。在

所以像这样：

^{pr2}$

但我不确定这是否比简单地搜索一个又一个前缀更有效，因为它需要在每一步都重建候选列表。在

Answer 1

我不知道有什么东西能做到这一点。在

但如果我要写它，我会尝试构建一个包含所有可能决策点的trie，并附带一个包含所有状态的向量。然后获取每个字符串，遍历trie直到找到最终匹配的节点，然后返回预编译的结果向量。在

如果你有很多前缀并且设置了k大，那么这个trie可能非常大。但是，如果你用分期付款的方式来创建它，而不是在数百万条弦上运行它，那么它可能是值得的。在