Problem B
Doublets
Languages
en
es
fr
pt
Un Doublet est une paire de mots dont la différence est d’une lettre au maximum ; par exemple, «booster» et «rooster» ou «rooster» et «roaster» ou «roaster» et «roasted».
Vous recevez un dictionnaire de $25\, 143$ mots écrits en minuscules, ne dépassant pas $16$ lettres chacun. Vous recevez ensuite un certain nombre de paires de mots. Pour chaque paire de mots, trouvez la séquence de mots la plus courte qui commence par le premier mot et se termine par le second, de sorte que chaque paire de mots adjacents soit un doublet. Par exemple, si l’on vous attribuait la paire d’entrées «booster» et «roasted», une solution possible serait : («booster», «rooster», «roaster», «roasted») à condition que ces mots soient tous dans le dictionnaire.
Entrée
Une entrée se compose du dictionnaire (avec au plus $25\, 143$ mots) suivi d’un certain nombre de paires de mots (au plus dix). Le dictionnaire se compose d’un certain nombre de mots, un par ligne, et se termine par une ligne vide. Les paires de mots d’entrée suivent ; les mots de chaque paire apparaissent sur une ligne, séparés par un espace.
Sortie
Pour chaque paire d’entrée, imprimez un ensemble de lignes commençant par le premier mot et se terminant par le dernier. Chaque paire de lignes adjacentes doit être un doublet. S’il existe plusieurs solutions minimales, n’importe laquelle fera l’affaire. S’il n’y a pas de solution, imprimez une ligne: «No solution.» Laissez une ligne vide entre les cas.
| Exemple d’entrée 1 | Exemple de sortie 1 |
|---|---|
booster rooster roaster coasted roasted coastal postal booster roasted coastal postal |
booster rooster roaster roasted No solution. |