Intersection deux chaînes de caractères

salut,
j'ai l'énoncé suivant:
Enoncé
Nous vous demandons d’écrire une fonction intersection(v, w) qui calcule l’intersection entre deux chaînes de caractères v et w.

On définit l’intersection de deux mots comme étant la plus grande partie commune à ces deux mots. Par exemple, l’intersection de "programme" et "grammaire" est "gramm", et intersection("salut","rien") renvoie le string vide "", puisqu'aucun caractère n'est commun.

Si plusieurs solutions sont possibles, prenez celle qui est d'indices les plus petits dans v (par exemple intersection("bbaacc", "aabb") renvoie "bb".

ce code ne donne pas de résultat valide :

Code:

---

1 2 3 4 5 6 7

def intersection(w,v): res = "" for i in range(len(w) - 1): for j in range(len(v) - 1): if w[i]==v[j]: res += w[i] return res

---

en fait le test donne
fail Résultat attendu pour intersection('aimer', 'marie') : 'a'
fail Résultat attendu pour intersection('crane', 'carne') : 'ne'
fail Résultat attendu pour intersection('parisien', 'aspirine') : 'ri'
fail Résultat attendu pour intersection('platine', 'plainte') : 'pla'
fail Résultat attendu pour intersection('cuvé', 'vécu') : 'cu'
fail Résultat attendu pour intersection('platine', 'plainte') : 'pla'
fail Résultat attendu pour intersection('programme', 'grammaire') : 'gramm'
ok Bon résultat pour intersection('salut', 'rien') : ''
fail Résultat attendu pour intersection('aabbcc', 'ccaa') : 'aa'

Salut,

Avant de coder, il faut décrire un algorithme (en français) que l'on essaie avec un papier et un crayon.
Et s'il a l'air de fonctionner, on peut s'aventurer à le coder.

Donc si je vous donne les mots "bbaacc" et "aabb" comment faites vous pour fabriquer l'intersection (en déroulant un algo. sur une feuille de parpier)?

- W

salut,
voilà un exemple de code qui donne une résultat un peu mieux:

Code:

---

1 2 3 4 5 6 7 8

def intersection(v,w): res = "" for i in range(len(v)): for j in range(len(w)): if v[i:]==w[j:]: while(v[i] not in res): res+= v[i] return res

---

ok Bon résultat pour intersection('ironique', 'onirique') : 'ique'
ok Bon résultat pour intersection('crane', 'carne') : 'ne'
fail Résultat attendu pour intersection('aimer', 'marie') : 'a'
ok Bon résultat pour intersection('argent', 'gérant') : 'nt'
fail Résultat attendu pour intersection('programme', 'grammaire') : 'gramm'
ok Bon résultat pour intersection('salut', 'rien') : ''
fail Résultat attendu pour intersection('aabbcc', 'ccaa') : 'aa'

Salut.

J'imagine que cet exercice a pour objectif de te faire travailler avec des slices.

Comme te l'a suggéré wiztricks, il faut essayer de représenter le problème sur un bout de papelard ou dans un éditeur de texte.

Exemple pour les 3 premières décompositions d'un mot.

Code:

---

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

mot = 'carne'   - step 5 carne => mot[0:step + 0]   indice max : 0   - step 4 carn => mot[0:step + 0] arne => mot[1:step + 1]   indice max : 1   - step 3 car => mot[0:step + 0] arn => mot[1:step + 1] rne => mot[2:step + 2]   indice max : 2

---

On cherche maintenant la relation qu'il y a entre le step et l'indice max des slices.
On arrive à déduire que l'indice max vaut len(mot) - step, c'était pas trop dur :mrgreen:

A savoir :
- Pour résoudre cet exercice, 2 simples boucles for suffisent, pas besoin de while.

Ce que tu devrais déjà savoir :
- On peut décrémenter une valeur avec le range range(len(mot), 0, -1)- On peut à l'aide de in demander à python si un chaîne se situe dans une autre 'aa' in 'aabb'

Citation:

---

Envoyé par wiztricks

Donc si je vous donne les mots "bbaacc" et "aabb" comment faites vous pour fabriquer l'intersection (en déroulant un algo. sur une feuille de papier)?

---

J'écris v = "aabb" et w = "bbaacc" (pour simplifier et en remarquant que l'intersection ne sera jamais plus grande que la plus petite chaine).
Ce qui permet de reformuler l'intersection comme étant la plus grande sous chaîne de v contenue dans w.

Pour ce faire, il faut savoir fabriquer les sous-chaines de v et savoir tester la condition "est dans w".

Côté sous-chaînes de v.
Il y a celles qui commencent au premier caractère: a, aa, aab, aabb;
celles qui commencent au second: a, ab, abb; puis au 3ème: b, bb; et enfin au 4ème et dernier: b.

Le but étant de "programmer", on essaie de essaie de dérouler cela pour voir comment çà va pouvoir marcher.
1ère étape: on teste les sous-chaînes qui commencent au premier caractère.

1.0: a est dans w => intersection = a
1.1: aa est dans w et aa est plus grand que intersection =>intersection = aa
1.2: aab n'est pas dans w

Ici, on peut remarquer qu'il est inutile de tester aabb puisque aab n'est pas dans w.
2ème étape: on teste les sous-chaînes qui commencent au 2nd caractère.
On peut alors remarquer que l'intersection ayant déjà 2 caractères, inutile de tester les sous-chaines en ayant moins.

2.0: abb n'est pas dans w.

Et là on peut constater que la longueur de v étant 4, les sous-chaînes qui commencent au 3ème et 4ème caractères ont une longueur inférieure ou égale à celle de l'intersection: pas la peine de tester.

Maintenant que j'ai fait mon boulot d'analyse du problème et d'esquisse de la solution... Je peux m'aventurer à coder:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

def intersection(v, w): ix = '' min_ = min(len(v), len(w)) for s in range(len(v)): if len(ix) >= min_ - s: break for e in range(s + len(ix), min_): t = v[s:e+1] if t not in w: break if len(t) >= len(ix): ix = t return ix

---

et le code ne fait que traduire ce que j'ai raconté en "français" ni plus, ni moins.

- W

La solution de wiztricks est un bon exercice pour énumérer les souschaînes d'une chaîne mais elle est malheureusement très lente à exécuter. Si ton objectif n'est pas de t'entraîner mais d'avoir un code efficace il faut éviter d'énumérer toutes les souschaînes possibles.

Une approche raisonnablement simple est celle par programmation dynamique, elle se déroule en 4 étapes:
In: v, w: string de longueur m, n

1. Initialisation d'une matrice m+1×n+1 remplie de 0 nommée tab; Deux entiers max_value, max_i initialisés à 0
2. Parcours du tableau par ligne croissante (i) en commençant à 1, colonnes croissante (j) en commençant à 1. tab[i][j] ← 0 si v[i-1]!=w[j-1]; 1 + tab[i-1][j-1] sinon
3. Mise à jour du maximum trouvé : en chaque position du tableau, si tab[i][j] > max_value, alors max_i ← i
4. Reconstruction de la chaîne à retourner : slice v entre les indices max_i-max_value et max_value

Out: slice de v

En terme de code cela peut être implémenté ainsi:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

def intersection(v, w): m, n = len(v), len(w) tab = [[0] * (n+1) for _ in range(m+1)] ma = (0, 0) for i in range(1, m+1): for j in range(1, n+1): tab[i][j] = (0 if v[i-1]!=w[j-1] else 1+tab[i-1][j-1]) if tab[i][j] > ma[0]: ma = (tab[i][j], i)   s = v[ma[1]-ma[0]:ma[1]] return s

---

Ce code a une complexité de O(m×n) contre O(n²×m) au minimum si on énumère les souschaînes.
Il existe d'autres algorithmes plus efficaces encore mais plus difficiles à mettre en place (SuffixTree, RollingHashes).

Citation:

---

Envoyé par pLOPeGG

La solution de wiztricks est un bon exercice pour énumérer les souschaînes d'une chaîne mais elle est malheureusement très lente à exécuter.

---

Où as-tu vu que j'énumérais toutes les sous/chaines?

- W

Citation:

---

Envoyé par wiztricks

Où as-tu vu que j'énumérais toutes les sous/chaines?

---

Petit raccourci de langage erroné, tu coupes bien les branches qui n'aboutiront pas. Je ne suis pas sur que ça change quelque chose dans la complexité de l'algorithme.

Citation:

---

Envoyé par pLOPeGG

Je ne suis pas sur que ça change quelque chose dans la complexité de l'algorithme.

---

Encore faut-il prendre le temps de la calculer.
Ce qui est peut être compliqué j'en conviens... mais ans çà, on ne sait pas.

- W

Salut.

pLOPeGG, avant de parler d'optimisation, faudrait un peu tester ce que vaut ton code en terme de performances, bon déjà, ça plante avec certains tests, puis ton code est de 3 à 4 × plus lent que celui de wiztricks :mrgreen:

Sinon ma soluce d'après ce que j'avais décrit se résumait à faire :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

def intersection(v, w) : len_v = len(v) # print('### ', v, w) for size in range(len_v, 0, -1) : # print(' -- Par taille', size) for i in range(len_v - size + 1) : extrait = v[i:i + size] # print(' - Extrait', extrait) if extrait in w : return extrait return ''

---

Salut,

Citation:

---

Envoyé par bistouille

Sinon ma soluce d'après ce que j'avais décrit se résumait à faire

---

Ta solution est bien meilleure car elle coupe les branches automatiquement => moins de code.
La différence est dans la construction de l'arbre des sous-chaînes: on commence par la plus grande, puis celles qui ont 1 caractère de moins,...
Côté complexité, on ne doit pas être si différents (les cas favorables compensant les cas défavorables) sinon que çà devrait être plus simple à calculer (mais je n'ai pas le temps de faire l'exercice).

- W

Citation:

---

Envoyé par wiztricks

Côté complexité, on ne doit pas être si différents (les cas favorables compensant les cas défavorables)

---

Oui, c'est du pareil au même niveau complexité.

Code:

---

1 2 3 4 5 6 7 8 9 10

def intersection(v, w): longv = len(v) comb = 0 for i in range(longv, 0, -1): for n in range(comb+1): if v[n:i+n] in w: return v[n:i+n] comb += 1 return ''

---