在我的应用程序中,我有多达数百万个短字符串(大多数短于 32 个字符)。我想实现一个带有附加列表的搜索框,该列表仅包含包含在搜索框中输入的整个字符串的元素。我怎样才能预先建立一个索引来快速找到这样的字符串?所有排序的 STL 容器检查整个字符串。
对于输入的搜索字符串“str”,我需要找到所有包含“str”的字符串:“main street”、“struve”、“ustr”等。
最佳答案
您可以构建一个 Permuterm indexes .
对于“struve”,您将插入 Radix tree (或通用搜索树):
struve$
truve$s
ruve$st
uve$str
ve$stru
e$struv
$struve
要搜索中缀,您将从根节点搜索匹配的前缀字符串。
关于c++ - "contains string"的快速索引,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2085445/