Forum des informaticiens de la FST
L'équipe du Forum Info-Fst, vous souhaite la bienvenue parmi nous.

Aide: la plus longue sous chaine commune entre 2 chaines

Voir le sujet précédent Voir le sujet suivant Aller en bas

Enervé Aide: la plus longue sous chaine commune entre 2 chaines

Message par (Le_king) le Dim 19 Oct - 14:31

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 Crying or Very sad Crying or Very sad Crying or Very sad Crying or Very sad Crying or Very sad Crying or Very sad
avatar
(Le_king)
VIP
VIP

Masculin Nombre de messages : 793
Age : 66
Section et Année : Mastère Réseau et Télécommunication
Localisation : http://info-fst.superforum.fr
Date d'inscription : 13/10/2006

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Enervé Re: Aide: la plus longue sous chaine commune entre 2 chaines

Message par (Le_king) le Dim 19 Oct - 14:46

aya winhom elli samio fi rwe7hom les developpeurs!!!!
avatar
(Le_king)
VIP
VIP

Masculin Nombre de messages : 793
Age : 66
Section et Année : Mastère Réseau et Télécommunication
Localisation : http://info-fst.superforum.fr
Date d'inscription : 13/10/2006

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Enervé Re: Aide: la plus longue sous chaine commune entre 2 chaines

Message par 407 le Dim 19 Oct - 14:49

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

_________________

avatar
407
Admin
Admin

Masculin Nombre de messages : 3451
Age : 107
Section et Année : promo2008 DOTA - WoW
Localisation : Dans vos Coeurs
Date d'inscription : 24/10/2006

Voir le profil de l'utilisateur http://www.torrentz.com

Revenir en haut Aller en bas

Enervé Re: Aide: la plus longue sous chaine commune entre 2 chaines

Message par Le_Chaba7 le Dim 19 Oct - 14:57

merci 407 pour le lien Smile
avatar
Le_Chaba7
VIP
VIP

Masculin Nombre de messages : 841
Age : 31
Section et Année : inchalah I3
Date d'inscription : 07/04/2006

Voir le profil de l'utilisateur http://www.etudes-astuces.org

Revenir en haut Aller en bas

Enervé Re: Aide: la plus longue sous chaine commune entre 2 chaines

Message par (Le_king) le Dim 19 Oct - 15:04

merci 407 MAIS C PA CA
EXP
MONTEAU
CHAPEAU

SOUS CHAINE= EAU DE LONGEUR 3
avatar
(Le_king)
VIP
VIP

Masculin Nombre de messages : 793
Age : 66
Section et Année : Mastère Réseau et Télécommunication
Localisation : http://info-fst.superforum.fr
Date d'inscription : 13/10/2006

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Enervé Re: Aide: la plus longue sous chaine commune entre 2 chaines

Message par 407 le Dim 19 Oct - 15:13

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

_________________

avatar
407
Admin
Admin

Masculin Nombre de messages : 3451
Age : 107
Section et Année : promo2008 DOTA - WoW
Localisation : Dans vos Coeurs
Date d'inscription : 24/10/2006

Voir le profil de l'utilisateur http://www.torrentz.com

Revenir en haut Aller en bas

Enervé Re: Aide: la plus longue sous chaine commune entre 2 chaines

Message par marbus380 le Dim 19 Oct - 16:13

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
avatar
marbus380
Membre fidèle
Membre fidèle

Masculin Nombre de messages : 166
Age : 32
Section et Année : I4
Localisation : Tunis - Tunisia
Date d'inscription : 11/12/2007

Voir le profil de l'utilisateur http://bientot.com

Revenir en haut Aller en bas

Enervé Re: Aide: la plus longue sous chaine commune entre 2 chaines

Message par (Le_king) le Dim 19 Oct - 16:22

el youm bech na3tik w tawali inti Le_king 407
avatar
(Le_king)
VIP
VIP

Masculin Nombre de messages : 793
Age : 66
Section et Année : Mastère Réseau et Télécommunication
Localisation : http://info-fst.superforum.fr
Date d'inscription : 13/10/2006

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Enervé Re: Aide: la plus longue sous chaine commune entre 2 chaines

Message par (Le_king) le Dim 19 Oct - 16:30

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
avatar
(Le_king)
VIP
VIP

Masculin Nombre de messages : 793
Age : 66
Section et Année : Mastère Réseau et Télécommunication
Localisation : http://info-fst.superforum.fr
Date d'inscription : 13/10/2006

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Enervé Re: Aide: la plus longue sous chaine commune entre 2 chaines

Message par marbus380 le Dim 19 Oct - 16:45

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
avatar
marbus380
Membre fidèle
Membre fidèle

Masculin Nombre de messages : 166
Age : 32
Section et Année : I4
Localisation : Tunis - Tunisia
Date d'inscription : 11/12/2007

Voir le profil de l'utilisateur http://bientot.com

Revenir en haut Aller en bas

Enervé Re: Aide: la plus longue sous chaine commune entre 2 chaines

Message par Le_Chaba7 le Dim 19 Oct - 23:51

bonjour

najmou ne5dmouha manghir matrice pour le cas de deux chaines de caracteres
avatar
Le_Chaba7
VIP
VIP

Masculin Nombre de messages : 841
Age : 31
Section et Année : inchalah I3
Date d'inscription : 07/04/2006

Voir le profil de l'utilisateur http://www.etudes-astuces.org

Revenir en haut Aller en bas

Enervé Re: Aide: la plus longue sous chaine commune entre 2 chaines

Message par 407 le Lun 20 Oct - 0:06

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.

_________________

avatar
407
Admin
Admin

Masculin Nombre de messages : 3451
Age : 107
Section et Année : promo2008 DOTA - WoW
Localisation : Dans vos Coeurs
Date d'inscription : 24/10/2006

Voir le profil de l'utilisateur http://www.torrentz.com

Revenir en haut Aller en bas

Enervé Re: Aide: la plus longue sous chaine commune entre 2 chaines

Message par elGrand le Lun 20 Oct - 5:47

m3allem  407 
avatar
elGrand
VIP
VIP

Masculin Nombre de messages : 206
Age : 34
Section et Année : Mastère Professionnel Administration des Réseaux - Supcom-
Date d'inscription : 31/12/2007

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Enervé Re: Aide: la plus longue sous chaine commune entre 2 chaines

Message par (Le_king) le Lun 20 Oct - 12:12

Aide::
ken ma9la9touch meni
algo pour determiner le nbre de couple en commun
avatar
(Le_king)
VIP
VIP

Masculin Nombre de messages : 793
Age : 66
Section et Année : Mastère Réseau et Télécommunication
Localisation : http://info-fst.superforum.fr
Date d'inscription : 13/10/2006

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Enervé Re: Aide: la plus longue sous chaine commune entre 2 chaines

Message par Le_Chaba7 le Lun 20 Oct - 12:29

Le_king a écrit:Aide::
ken ma9la9touch meni
algo pour determiner le nbre de couple en commun
explique stp
avatar
Le_Chaba7
VIP
VIP

Masculin Nombre de messages : 841
Age : 31
Section et Année : inchalah I3
Date d'inscription : 07/04/2006

Voir le profil de l'utilisateur http://www.etudes-astuces.org

Revenir en haut Aller en bas

Enervé Re: Aide: la plus longue sous chaine commune entre 2 chaines

Message par (Le_king) le Lun 20 Oct - 13:07

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
avatar
(Le_king)
VIP
VIP

Masculin Nombre de messages : 793
Age : 66
Section et Année : Mastère Réseau et Télécommunication
Localisation : http://info-fst.superforum.fr
Date d'inscription : 13/10/2006

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Enervé Re: Aide: la plus longue sous chaine commune entre 2 chaines

Message par Le_Chaba7 le Lun 20 Oct - 13:42

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);
}
}
avatar
Le_Chaba7
VIP
VIP

Masculin Nombre de messages : 841
Age : 31
Section et Année : inchalah I3
Date d'inscription : 07/04/2006

Voir le profil de l'utilisateur http://www.etudes-astuces.org

Revenir en haut Aller en bas

Enervé Re: Aide: la plus longue sous chaine commune entre 2 chaines

Message par marbus380 le Lun 20 Oct - 13:47

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
avatar
marbus380
Membre fidèle
Membre fidèle

Masculin Nombre de messages : 166
Age : 32
Section et Année : I4
Localisation : Tunis - Tunisia
Date d'inscription : 11/12/2007

Voir le profil de l'utilisateur http://bientot.com

Revenir en haut Aller en bas

Enervé Re: Aide: la plus longue sous chaine commune entre 2 chaines

Message par (Le_king) le Lun 20 Oct - 15:39

winek ya 407
avatar
(Le_king)
VIP
VIP

Masculin Nombre de messages : 793
Age : 66
Section et Année : Mastère Réseau et Télécommunication
Localisation : http://info-fst.superforum.fr
Date d'inscription : 13/10/2006

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Enervé Re: Aide: la plus longue sous chaine commune entre 2 chaines

Message par elanouar le Lun 20 Oct - 18:40

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

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 Sleep

a+.
avatar
elanouar
Membre trés actif
Membre trés actif

Masculin Nombre de messages : 408
Age : 32
Section et Année : i4 // ye hasra
Localisation : on the moon
Date d'inscription : 12/02/2007

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Enervé Re: Aide: la plus longue sous chaine commune entre 2 chaines

Message par (Le_king) le Mar 21 Oct - 3:56

pa encore j n ai pa trouvé la solution
avatar
(Le_king)
VIP
VIP

Masculin Nombre de messages : 793
Age : 66
Section et Année : Mastère Réseau et Télécommunication
Localisation : http://info-fst.superforum.fr
Date d'inscription : 13/10/2006

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Enervé Re: Aide: la plus longue sous chaine commune entre 2 chaines

Message par (Le_king) le Mar 21 Oct - 7:40

winkom ya jme3a rahi 7keya sur et urgent
avatar
(Le_king)
VIP
VIP

Masculin Nombre de messages : 793
Age : 66
Section et Année : Mastère Réseau et Télécommunication
Localisation : http://info-fst.superforum.fr
Date d'inscription : 13/10/2006

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Enervé Re: Aide: la plus longue sous chaine commune entre 2 chaines

Message par Le_Chaba7 le Mar 21 Oct - 10:01

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

Masculin Nombre de messages : 841
Age : 31
Section et Année : inchalah I3
Date d'inscription : 07/04/2006

Voir le profil de l'utilisateur http://www.etudes-astuces.org

Revenir en haut Aller en bas

Enervé Re: Aide: la plus longue sous chaine commune entre 2 chaines

Message par 407 le Mar 21 Oct - 10:19

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

_________________

avatar
407
Admin
Admin

Masculin Nombre de messages : 3451
Age : 107
Section et Année : promo2008 DOTA - WoW
Localisation : Dans vos Coeurs
Date d'inscription : 24/10/2006

Voir le profil de l'utilisateur http://www.torrentz.com

Revenir en haut Aller en bas

Enervé Re: Aide: la plus longue sous chaine commune entre 2 chaines

Message par Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Voir le sujet précédent Voir le sujet suivant Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum