"包含字符串"的快速索引

Question

在我的应用程序中,我有数百万个短字符串(大多数短于32个字符).我想实现一个带有附加列表的搜索框,该列表仅包含包含在搜索框中输入的整个字符串的元素.我怎样才能预建一个索引来快速找到这样的字符串？所有已排序的STL容器都会检查整个字符串.

对于输入的搜索字符串"str",我需要找到所有包含"str"的字符串:"main street","struve","ustr"等.

Answer 1

您可以构建Permuterm索引.

对于"struve",您将插入到Radix树(或通用搜索树)中:

struve$
truve$s
ruve$st
uve$str
ve$stru
e$struv
$struve

要搜索中缀,您将从根节点搜索匹配的前缀字符串.

Answer 2

您可以从查看trie开始。尽管它们主要用作前缀树，但数据结构本身可以适应更快的一般搜索。