Une ptite curiosité.
Je vous propose d'implémenter un autocomplete.
Pour rappel, un autocomplete c'est:
Je tape quelques caractères, et l'autocomplete me propose des suggestions en accord avec ce que j'ai tapé.
Nous allons simplifier le problème par:
Je tape k caractères: a_0a_1...a_{k-1} (a_i pris dans l'alphabet français)
l'autocomplète me propose les 10 premiers mots commençant par
a_0a_1...a_{k-1}
(éventuellement moins si y a moins de mots satisfaisant l'input)
* Par premier, nous entendons que les mots sont ordonnés par ordre lexical. (a < b, a < aa).
(Nous simplifions pour l'instant le pb pour ne pas se soucier des fautes de frappe, de datamining, user history et autres.)
note: on ne s'intéresse pas à comment on affiche les propositions ni comment on demande la saisie (stdin stdout sont suffisants); ce qui nous intéresse est la structure de donnée, l'algorithme d'insertion/modification, l'algorithme pour trouver les occurrences.
Pour avoir un jeu de données commun et vraisembable, partons de la liste de mots http://www.pallier.org/ressources/dicofr/dicofr.html
Le but premier est d'être le plus rapide possible en temps pour l'algorithme de recherche.
note: comme je vs vois venir, si vous décidez de faire les bourrins de la mémoire, alors majorons à 1Go l'espace de stockage disponible
(ce qui est inadmissible pour un usage classique mais soyons fous!).
