Text predictor when you type in characters <Beginner question>

[localp]

I need to create a C++ program, that one could get a list of suggestions when he's typing. for example: when we type the letter 'A', a list of words that start with the letter A should display. then when we type another letter 'P', the words should filter and all words that start with 'AP' should be listed, finally. the word 'APPLE' will be selected upon click.

I hope I made my scenario clear. I got a few questions here;

1.) When a person types a letter; say 'A', how can we list all the words below it, do we have to get the values from a database? (and it should be really fast too) or is there any other easy way?

2.) In a mobile phone we have the feature called 'T9', when we type a character it keeps on suggesting words. So is there a small or whatsoever database? how is it working?

3.) Are there any sample programs, that could start working on?

[mike_2000_17]

First of all, you need some kind of GUI for this, cin / cout won't be good enough for sure (or a least a lot of trouble). So figure out what you want to use first (Qt, MFC, SDL, whatever..), then you can start to solve that problem.

Second, I'm sure there are already some tools for Qt or MFC that do this.

Finally, yes you will need a database or something to get a dictionary. These would be OS-specific and package-specific (linux). I can't help you much further with that. If you are up for it you can check something like KSpell (open-source spell-checker for linux, takes words and matches them to a dictionary to give suggestions if an exact match is not found), but I presume the source-code will be large.

[localp]

Do you know of a good search algorithm (after all its all about matching the word with the dictionary) that i could use ?

[mike_2000_17]

Well.. if the dictionary is in a file and in alphabetical order, then a binary search would probably be good enough. But if you deal with a database (which I recommend), then those search algorithm are included in the database server (MySQL, or any other you have access to) so all you have to do is say "find <first_characters>*" and it will find everything that start with your first characters (look up SQL query language for more details on that). You can be pretty sure that the search algorithms in the database is far more efficient than you could ever program yourself (there are people who make a living at perfecting those search algorithms).