Law*_*ton 3 c++ database algorithm search
我想创建一个库书籍标题数据库,可以有效地搜索子字符串匹配.也就是说,如果我搜索"编程",那么将返回包含单词编程的所有书名.该数据库可以被预处理并且将完全存储在存储器中.
什么是有效的数据结构和搜索算法来解决这个问题？我想完全用C++实现它,所以请不要第三方库.
ami*_*mit 6
后缀树是子字符串搜索的有效数据结构.
这个想法是: 创建你的后缀树数据结构,并从每个叶子连接到这个后缀代表的书/ s相关的条目. 在查询时间 - 使用子字符串遍历树 - 并从您到达的终点(最长匹配) - 执行一些遍历(例如DFS)并检索与查询是前缀的所有后缀相关的所有条目.
当然,如果你只想要单词而不是所有子串,一个地图(基于树/散列)可能就足够了,并且更容易实现和使用(该类型应该是map<string,list<book> >例如基于树的方法,它将映射从每个单词到一个列表,其中包含标题中包含该单词的所有书籍. 您还可以使用trie来实现地图.
map<string,list<book> >
归档时间：
12 年，10 月 前
查看次数：
2179 次
最近记录：