Le connaissant, ça ne m'étonnerait pas que ce soit ce qu'il ait proposé ...
Ça ne sert à rien d'employer des mots compliqués si c'est pour se planter sur l'orthographe :P
Ça sert à rien d'employer des noms de variables si compliqués si c'est pour se planter sur son algo :P
Le tout est de trouver comment stocker toutes les sous-chaînes présentes : les stocker tel quel ne passe pas en
mémoire et demandera trop de temps pour les trier. On associe donc à chaque sous-séquence un nombre (quelqu'un
pourrait me dire si c'est ça le hachage d'ailleurs ?) : on considère qu'une lettre représente un chiffre parmi {0, 1,
2, 3} et que l'ensemble forme un nombre écrit en base 4. Le nombre associé à une sous-chaîne est en fait ce nombre
écrit en base 10.
C'est une fonction de hachage parfaite (qui ne génère pas de collisions) ... si on utilise une table de 2³⁰ éléments
... (puisque les sous-chaînes sont de longueurs
@ alex3er : Je te rassure le code OCaml que j'ai écrit et qui utilise des tables de hachage est beaucoup plus compact et
passe aussi tous les tests ...
Là disons que j'ai implémenté ça ... pour le fun, mais que je n'aurai jamais fait ça lors d'une demi-finale (enfin j'en
sais rien, je ne suis encore jamais allé en demi-finale xD). C'est d'ailleurs sans doute pour ça que j'ai récolté que 10
points à la question ;p
@ jojomolo : Erf ... En fait, c'est pas vraiment évident à expliquer sans un papier et un crayon, mais je veux bien
réessayer xD
Globalement si on fait un schéma on se rend bien compte que ça marche, là où il faut réfléchir un peu c'est juste sur
l'analyse de complexité amortie.
Grosso-modo tu veux stocker n éléments dans un tableau, en ayant des fonctions d'insertion et de recherche (l'élément i
appartient-il à mon tableau ?) efficaces. Plutôt que de stocker ça dans un seul grand tableau trié (ce qui rendrait la
fonction d'insertion pas terrible : imagine que tu insères toujours au début du tableau, il faudrait à chaque fois tout
redécaler), on utilise plusieurs tableaux de tailles différentes.
Mettons que n s'écrive en binaire n.(k-1),...,n.(1),n.(0).
On a un premier tableau A[0] est de taille 1, A[1] de taille 2, A[2] de taille 2²=4, etc.
On décide de ranger dans A[i] exactement 2\^i éléments si et seulement si on a n.(i) = 1. (*)
De plus les éléments au sein du tableau A[i] doivent être rangés dans l'ordre croissant.
On aura bien stocké dans nos k tableaux somme(n.(i)*2\^i, i=0 à k-1) = n éléments.
Après l'opération d'insertion vise principalement à s'assurer qu'on garde la propriété (*), et que les éléments sont
toujours triés au sein d'un tableau A[i].
L'opération de recherche se contente de parcourir nos k tableau, en effectuant une recherche dichotomique au sein de ce
tableau (d'où la nécessité de garder les éléments triés).
Au niveau des algo' proposés aux questions 3 et 4, globalement je vois les mêmes idées qui reviennent, mais je me
demande si quelqu'un a tenté autre chose que l'algo de prog' dyn' pour la distance de levenshtein (question 4), ou en
tout cas une autre variante qui ne limite pas juste la plage de recherche à ±100 ?
Prologin
2024
