PAT 解题报告 1022. Digital Library (30)

题目描述:

给一个图书馆的图书数据库, 每条记录有一系列属性:

  • Line #1: the 7-digit ID number;
  • Line #2: the book title — a string of no more than 80 characters;
  • Line #3: the author — a string of no more than 80 characters;
  • Line #4: the key words — each word is a string of no more than 10 characters without any white space, and the keywords are separated by exactly one space;
  • Line #5: the publisher — a string of no more than 80 characters;
  • Line #6: the published year — a 4-digit number which is in the range [1000, 3000]

然后给出query, 输出所有满足query的记录id。

算法分析:

做一个倒排表, 也就是对每一条记录, 不是用id去index那些属性, 而是用属性作为index, id所谓内容, 类似inverted index. 举例如下: 比如这条记录

1111111
The Testing Book
Yue Chen
test code debug sort keywords
ZUCS Print
2011

那么我们拆分关键字test code debug sort keywords, make hash_table[test].insert( 111111), hashtable.insert( 1111111). 对所有的关键字做一个索引, 同理hash_table[2011].insert(111111), hash_tabl[ZUCS Print].insert(1111111), 反正就是对可能的query预先都做好索引, 等query来的时候不用线性扫描整个数据库, 利用hash的话基本上可以做到常数时间找到符合某一个query的所有结果集.

注意点:

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on July 12, 2013