Aide: la plus longue sous chaine commune entre 2 chaines

svp algo o code en c o en java
pour determiner la plus longue sous chaine commune entre deux chaines

aman c tres sur svvvvvvvvvvvvvp  

aya winhom elli samio fi rwe7hom les developpeurs!!!!

Salut le king,
est ce que tu veut la solution a ce genre de prblm 4 7

merci 407 pour le lien

merci 407 MAIS C PA CA
EXP
MONTEAU
CHAPEAU

SOUS CHAINE= EAU DE LONGEUR 3

Bsr le king,
bon voila deux liens j'espére que ca t'aidera car je pense que c'est ce que tu cherche :
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
http://www-igm.univ-mlv.fr/~lecroq/seqcomp/node4.html

Explication + détails + algo.

PS: pour t'aider dans tes recherches essai avec ca : "Longest Common Subsequence" sur google et t'aura des milliers de liens.
++ 4:good:7

Le King, je te propose une solution en Java, le meilleur langage pour résoudre tout probléme
essaie de prendre une chaine
ensuite teste avec la méthode ch1.contains(x)
alors que ton x est une sous chaine de la chaine ch2
et fait boucler sur la chaine ch2 sur tout sa longueur en changeant d'indice du substring
le nombre de boucle à faire est
z=la taille de ch2
int j=1
j'explique :
for (int i=0, i{
for (int j=i+j,j if ch1.contains(ch2.substring(i,j))
{
ajouter dans tabeau de string la valeur ch2.substring(i,j)
}
}
ensuite parcourir ton tableau de string (il contiendra tout les sous chaine commune entre ch1 & ch2)
et test si tab[i].size ==>faire tri & extraire max
et oooooopppp , voila le résultat obtenu
j'espére avoir bien répondu à ta question
Je reste à disposition pour tout complément d'info


Java is the Best

el youm bech na3tik w tawali inti Le_king 407

merci  marbus380 mais le7eya s3iba chwiya
metet5dem ken b matrice w zid chouf
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
donc grand merci pour 407

Amigo Le_King , je suis entrain de croiser des indices de tableaux==> ça donne par défaut une matrice :-)
et le tableaux final résultant contiendrai tout les sous chaines d'1 à n caractéres commune entre, soit disant X et Y
ensuite du prendra ce que tu veux (la plus longue, la plus petite) as you like

bonjour

najmou ne5dmouha manghir matrice pour le cas de deux chaines de caracteres

Bonjour de rien Le king et merci chaba7 et aussi GJ a marbus380 d'avoir fait plus que moi et de s'être pencher sur le problème et essayer de trouver une solution meilleur 4:good:7

En tout cas le king tu a mnt pas une mais des solutions.

m3allem  407 

Aide::
ken ma9la9touch meni
algo pour determiner le nbre de couple en commun

Le_king a écrit:Aide::
ken ma9la9touch meni
algo pour determiner le nbre de couple en commun

explique stp

par exemple

NELSON   &    NEILSEN

LES COUPLES :   

NE EL LS SO ON    &    NE EI IL LS SE EN

2 COUPLES EN COMMUN ( NE,LS).
ET MERCI D AVANCE

Le_king a écrit:par exemple

NELSON   &    NEILSEN

LES COUPLES :   

NE EL LS SO ON    &    NE EI IL LS SE EN

2 COUPLES EN COMMUN ( NE,LS).
ET MERCI D AVANCE

behi je vais faire l affichage des couples (tu peux les stockets dans un tableau)

couple(char *mot1 , char *mot2)
{
char s[3];

for ( i = 0 ; i < strlen(mot1)-1 ; i ++ )
{
strncpy( s, *mot1+i,2);
if( strstr(mot2,s) )
puts(s);
}
}

King, parcours le tableau que t'ai mentionné dans mon dernier message
et chercher les tab[i].size=2 et tu auras la liste des tous les couples en commun
c'est aussi simple que possible

winek ya 407

Ahla bil king
alors je vais te donner la methode de resoltion mais pas la solution mechi bech

alors tu n a qu a rechercher les chaines communes entre les deux chaines ,tu les empiles dans un vecteur
Tu optimise votre vecteur(histoire de perfectionnement,optimiser le temps de parcours et du traitement// tu peut oublier cette partie;mais on tout cas c une fonction si je me rappel bien c Finalize())
puis cree un tableau qui possede un le meme longeur du vecteur
tu parcours le vecteur et a chaque element tu capte la longuer de la chaine et tu l enregistre dans le tableau,et n'oublie pas d'incrimenter un indice pour assurer la progression dans le tableau.
A la fin tu n'a que chercher la case qui possede le nombre le plus grand.
Et voila l'indice de la case qui possede le plus grand nbre c l indice de l emplacement de la plus grande chaine commune.
Pour finir tu n'a qu afficher le contenu
Voila qques fonctions;length()-->longeur de la chaine ,compare()--->comparer 2 chaines (faite attention c pas ==).

Inchallah mankounich gaulitt fi haja rani presque

a+.

pa encore j n ai pa trouvé la solution

winkom ya jme3a rahi 7keya sur et urgent

Le king je crois que j ai déjà proposé un programme C qui marche alors c à toi de jouer mnt

Salut,
perso j'ai trouvé qlq personnes qui on posé cette question sur d'autres fofo mais personne ne lui a donnée un algo en lui disant que c'est facile et qu'il suffisait de prendre les lettres du string S1 par couple et de faire avec les couple du string S2 et que c'était qu'un simple parcour de comparaison par couple.
En tout cas je vais voir ce que je trouve sinon c'est le meileur que j'ai trouvé jusqu'a mnt ++ 4:pirat:7