---

倒排表或倒排索引以词做索引，内容为包含该词的文档编号。倒排索引是目前 搜索引擎公司最对搜索引擎最常用的存储方式。

 

倒排文件也可以应用于非结构化的信息检索里面，如大量正文的文本索引。尤其当今搜索引擎需要对海量的正文文本信息进行检索的情况下，倒排文件的使用尤其重要。

对多个正文文本建立索引的基本思想就是，把正文看成一个一个的关键词的集合，然后用这些词组成一些适合快速检索的数据结构。一个倒排文件就是一个已经排好序的关键词的列表，其中每个关键词指向一个倒排表，该表中记录了该关键词出现的文档集合以及在该文档中的出现位置。如北大某院图书馆论文集的部分倒排表：

关键词

倒排表（所在文档编号，出现次数， 出现位置）

KMP

（#3307, 2, 5, 43）（#4615, 5, 0, 19, 34, 70, 143）

最小支撑树

（#2519, 1, 267）（#6742, 3, 19, 322, 526）……

贪心算法

（#2948, 3, 45, 267, 587）（#3693, 5, 39, 423, 765,809,1024）……

……

……

问题：

一个很大的字符串，如何在里面查找某个单词？