Ta besoin d'une fonction de comparaison de 2 chaines t'indiquant la position du premier caractère différent.
compare : String x String -> Entier
chaine commune = chaine_1[1..min(compare(chaine_i, chaine_j))-1]
donc tu peux lire séquentiellement ton tableau et à chaque comparaison tu garde la plus petite valeur entre le minimum courant et le résultat de la comparaison.
Complexité :
Soit l la longueur moyenne d'une chaine
compare(chaine1, chaine2) se fait en O(2l) = O(l)
Soit n la taille du tableau
chaine_commune(tableau) se fait en O(2l*n) = O(l*n)
Message édité par pains-aux-raisins le 01-09-2004 à 12:34:58
