iPhone Nano

Vous venez d'être embauché chez Apple qui a besoin de vous pour faire un programme pour le nouvel iPhone Nano. Sur cet appareil, l'écran tactile est tellement petit que lorsque l'on touche sur une lettre pour taper du texte, on est obligé de taper au moins 4 lettres d'un coup. L'iPhone doit alors reconstituer le mot souhaité en s'aidant d'un dictionnaire dans lequel les mots sont triés selon leur fréquence d'utilisation.

Vous devez donc écrire un programme qui prend en entrée des groupes de 4 lettres distinctes tapées par l'utilisateur, et qui calcule le mot le plus fréquent du dictionnaire que l'utilisateur ait pu essayer de taper. On vous garantit qu'il existe au moins un mot du dictionnaire qui convient.

• 1 <= D <= 10 000, où D est le nombre de mots du dictionnaire.
• 1 <= L <= 20, où L est la longueur d'un mot du dictionnaire.
• 1 <= N <= 20, où N est la longueur du mot tapé, c'est-à-dire le nombre de groupes de 4 lettres que votre programme doit prendre en entrée.

Pour simplifier, on vous garantit que tous les caractères utilisés sont des lettres minuscules non accentuées.

• La première ligne contient un entier : D.
• Les D lignes suivantes contiennent les mots du dictionnaire : un mot par ligne.
• La ligne suivante contient un entier : N.
• Les N lignes suivantes contiennent les groupes de 4 lettres détectés par l'écran de l'iPhone, dans l'ordre chronologique.

Vous devez afficher un mot sur une ligne : le mot le plus fréquent qui a pu être tapé par l'utilisateur.

Le dictionnaire est composé de 9 mots. Le plus fréquent d'entre eux est "franceioi", suivi de "nano", puis "apple", etc.

Le mot que l'utilisateur a voulu saisir comporte 5 lettres. La première lettre de ce mot est un 'a', un 'p', un 'o' ou bien un 'h'. La deuxième lettre est un 'r', un 'c', un 'p' ou un 'i', etc.

Les mots "ocaml" et "print" sont possibles, mais "ocaml" est plus fréquent donc c'est ce mot-là que l'on choisit. Voici comment faire apparaître ce mot :

apoh
rcpi
piua
mnod
dlte

Squelette de code C++ :

#include <cstdio>
#include <cstdlib>
#include <cstring>

const int MAX_NB_MOTS = 10000;
const int MAX_TAILLE_MOTS = 20;
const int TAILLE_GROUPE = 4; 
int nbMots, nbGroupes;
char dico[MAX_NB_MOTS][MAX_TAILLE_MOTS+1];
char groupes[MAX_TAILLE_MOTS][TAILLE_GROUPE+1];

int main()
{
   // lecture de l'entrée
   scanf("%d", &nbMots);
   for (int mot = 0; mot < nbMots; mot++)
      scanf("%s", dico[mot]);
   scanf("%d", &nbGroupes);
   for (int groupe = 0; groupe < nbGroupes; groupe++)
      scanf("%s", groupes[groupe]);
  
   // insérez votre code ici
   // le tableau dico[idMot][lettre] décrit les mots du dictionnaire
   // le tableau groupes[lettre][choix] décrit les lettres possibles
   //  pour la position 'lettre'
   // pour afficher un mot, utiliser l'instruction :
   // printf("%s\n", dico[idMot]);
   
   return 0;
}

Pratique : la fonction "strlen" retourne la longueur d'une chaîne.

Squelette de code Caml :

let scan_int () = Scanf.scanf " %d" (fun x -> x)
let scan_string () = Scanf.scanf " %s" (fun x -> x)
let show_string s = Printf.printf "%s\n" s
let nbMots = scan_int()
let dico = Array.init nbMots (fun _ -> scan_string())
let nbGroupes = scan_int()
let groupes = Array.init nbGroupes (fun _ -> scan_string())
let _ =
   (* insérer votre code ici *)
   (* dico.(idMot) décrit un mot du dictionnaire, et
      groupes.(pos) est un mot de 4 lettres qui correspond aux
      4 lettres tapées par l'utilisateur à la position pos.
   
   (* utilisez la fonction show_string pour afficher le résultat *)

Conseil : appuyez-vous sur les fonctions de la bibliothèque standard pour manipuler les chaînes.