Discussion :

[nicolas66]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[jobherzt]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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..

[Jean-Marc.Bourguet]

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

[nicolas66]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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


Nico.

[nicolas66]

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).

[nicolas66]

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

[jobherzt]

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.