Algorithme de plus grand sous-mot commun

Bonjour,

Pour les besoins d'un projet, j'aimerai trouver un algorithme donnait le plus grand sous-mot commun à deux chaînes de même longueur.

Exemple :

Code:

---

1 2 3 4

Chaine1 = "toto_va_bien" Chaine2 = "les_bielles!" Resultat -> "_bie"

---

Quelqu'un aurait-il une idée sur l'algorithme à écrire ? Merci d'avance.


Nico.

il y a l'algorithme "naif" qui consiste a parcourir les chaines butalement :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

une chaine a de longueur n une chaine b de longueur m   Sortie S = chaine vide   de i=1 a n de j=1 a m si a[i]=b[j] R=a[i] k=i+1 tant que a[k]=b[k] R=R.a[k] k=k+1 fin tant que si longueur de S < longuer de R S=R fin si fin si fin de fin de

---

a la louche, c'est peut etre bien du O(mn), mais surement un peu plus. on devrait pouvoir affiner : si on trouve un mot commun, on a parcouru cerain caracteres de b, et donc ca ne sert a rien de repartir a b[j+1], mais peut etre bien a b[j+k], ou un truc du genre..

http://en.wikipedia.org/wiki/Longest...string_problem

Après avoir testé l'algorithme de jobherzt, je me suis aperçu qu'il ne fonctionnait pas correctement. En réfléchissant un tantinet, je l'ai légèrement modifié pour arriver à cela :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

procedure PlusGrandSousMot( Chaine ch1, Chaine ch2 ) : Chaine début_procedure Chaine résultat, tmp Entier longueur_ch1 = ch1.longueur() Entier longueur_ch1 = ch2.longueur() Entier i, j, k1, k2   Pour i de 1 à longueur_ch1 début Pour j de 1 à longueur_ch2 début Si ch1[i] = ch2[j] alors début tmp = ch1[i] k1 = i + 1 k2 = j + 1   Tant_que k1 < longueur_ch1 et k2 < longueur_ch2 et ch1[k1] = ch2[k2] début tmp = tmp + ch1[k1] k1++ k2++ fin   Si résultat.longueur() < tmp.longueur() alors début résultat = tmp fin fin fin fin   Returner résultat fin_procedure

---

Cette fois-ci tout a l'air de fonctionner correctement. Il ne me reste plus qu'à paralléliser l'algorithme. Merci beaucoup pour votre aide :P


Nico.

Juste une dernière question : est-ce que vous avez une idée de la complexité exacte de l'algo que je viens d'écrire ? En fait je n'arrive pas à déterminer la complexité de la boucle while. Ce qui est certain c'est que la complexité est déjà supérieure à O(n * m).

Personne n'a d'idée sur la complexité de l'algo ?

oui, exact, j'utilisais le meme indice pour les 2 chaines... ce n'etait pas a prendre au pied de la lettre. mais le lien que te fournis Jean-Marc.Bourguet donne des solutions bien plus performantes.

pour ce qui est de la complexité, je dirais, en l'etat O(m.n.max(m,n)). mais comme je te le disais on peut l'ameliorer assea facilement en jouant sr les indices pour ne pas refaire 2 fois la meme chose. mais encore une fois, ca n'etait qu'une solution improvisée pour avoir un point de depart, il y a des solutions simples bien plus efficaces.