我们看到谷歌，火狐一些AJAX页面显示了可能的产品清单，同时用户键入的字符。

We see Google, Firefox some AJAX pages shows up list of probable items while user types characters.

有人可以给好的算法，数据结构实现自动完成？

Can someone give good algorithm,datastructure for implementing autocomplete ?

推荐答案

一个线索是一个可用于快速地找到匹配preFIX该字的数据结构

A trie is a data structure that can be used to quickly find words that match a prefix.

编辑：下面是一个例子，演示如何使用一个来实现自动完成 HTTP：/ /rmandvikar.blogspot.com/2008/10/trie-examples.html

Here's an example showing how to use one to implement autocomplete http://rmandvikar.blogspot.com/2008/10/trie-examples.html

下面是3个不同的自动完成实现的比较 （尽管它在Java中没有C ++）。

Here's a comparison of 3 different auto-complete implementations (though it's in Java not C++).

* In-Memory Trie
* In-Memory Relational Database
* Java Set

在查找键，线索稍高于设置执行速度更快。两个轮胎与集比关系DB溶液好位快

When looking up keys, the trie is marginally faster than the Set implementation. Both the tire and the set are a good bit faster than the relation DB solution.

设置的安装成本比特里或DB解决方案更低。你必须决定是否你会建造新的wordsets频频，还是查找速度是更高的优先级。

The setup cost of the Set is lower than the Trie or DB solution. You'd have to decide whether you'd be constructing new "wordsets" frequently or whether lookup speed is the higher priority.

这些结果是在Java中，您的情况可能与C ++的解决方案有所不同。

These results are in Java, your mileage may vary with a C++ solution.