高效的质量字符串搜索问题

Question

问题:提供了一个大的静态字符串列表.由数据和通配符元素(*和？)组成的模式字符串.想法是返回与模式匹配的所有字符串 - 足够简单.

当前解决方案:我目前正在使用线性方法扫描大型列表,并根据模式对每个条目进行通配.

我的问题:是否有任何合适的数据结构可以存储大型列表,以便搜索的复杂性小于O(n)？

也许是类似于后缀的东西？我也考虑过在哈希表中使用双克和三克,但是根据返回的单词列表和模式的合并来评估匹配所需的逻辑是一场噩梦,而且我不相信它是正确的做法.

Answer 1

如果您不关心内存并且可以预处理列表，请创建每个后缀的排序数组，指向原始单词，例如，对于 ['hello', 'world']，存储以下内容：

[('d'    , 'world'),
 ('ello' , 'hello'),
 ('hello', 'hello'),
 ('ld'   , 'world'),
 ('llo'  , 'hello'),
 ('lo'   , 'hello'),
 ('o'    , 'hello'),
 ('orld' , 'world'),
 ('rld'  , 'world'),
 ('world', 'world')]

使用此数组通过模式片段构建候选匹配集。

例如，如果模式是，则使用子字符串 上的二进制截断*or*找到候选匹配，然后使用正常的通配方法确认匹配。('orld' , 'world')or

如果通配符更复杂，例如 ，则为和h*o构建候选集，并在最终线性全局之前找到它们的交集。ho