Q:

Autocompletion library in C++

I need an auto-completion routine or library in C++ for 1 million words. I guess I can find a routine on the net like Rabin–Karp. Do you know a library that does this. I don't see it in Boost. 
Also, is it a crazy idea to use MySql LIKE SQL request to do that ?
Thank you
EDIT: It is true that it is more suggestions than auto-completion that I need (propose ten words when the user typed the first 2 letters). I actually also have expressions "Nikon digital camera". But for a first version, I only need suggestions on "Ni" of Nikon and not on "digital camera".

A:

You don't have to use any crazy algorithm if you begin by preparing an index.
A simple Trie/Binary Search Tree structure, that keeps the words ordered alphabetically, would allow efficient prefix searches.
In C++, for example, the std::map class has the lower_bound member which would point in O(log N) to the first element that could possibly extend your word.

