Discussion :

[MrPchoun]

Bonjour

Je chercher à faire une fonction f(str1, str2, minLength) qui me retournerait toutes les sous strings communes à ces deux strings, d'une longueur minimum de minLength, et ce, en éliminant les répétitions. Exemple, str1 = "bonbon" et str2 = "bonheur", il n'y aurait qu'une substring en commun, "bon".

Pour penser le problème d'une manière un peu plus abstraite (même si je n'ai pas encore la solution) je pense utiliser un tableau d'équivalence dont voici l'exemple, pour str1 = "abcdbcde" et str2 = "abcdeab" :



Et donc, mon problème consiste en fait "simplement" à trouver l'ensemble des points violets (i,j) tels que :
str1[i] = str2[j] et (i,j) > 1
il n'y ait qu'un seul point violet par axe
il y ait le maximum de cases vertes qui deviennent violettes

Et là c'est le blanc J'ai essayé en faisant des sommes par axes, des trucs, des machins, dans tous les sens, même un semblant d'arbre, mais j'aimerais éviter la solution des arbres et je suis sûr qu'il y a un moyen plus souple de résoudre cela, mais vraiment, je n'arrive pas à me représenter la solution dans ma tête..

Quelqu'un peut-il m'aider ?

[Flodelarab]

Bonjour

Sous Linux, je ferais un truc en une ligne comme ça, pour commencer:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
$ awk -F '' 'FNR==NR{for (i=1;i<=NF;i++) {n[$i]=int(n[$i]);tab[i]=$i;n[$i]++;deb[$i,n[$i]]=i;} next;} {for (i=1;i<=NF;i++) for (j=1;j<=int(n[$i]);j++) {c=0; d=deb[$i,j]; while (tab[d+c]==$(i+c)) {if ($(i+c)=="") break; printf $(i+c);c++;} print "";} }'  fichier1.txt fichier2.txt
abcd
bcd
bcde
cd
cde
d
de
e
ab
b
b

Pour chaque lettre de la deuxième chaîne (dans le fichier2.txt), il écrit la correspondance la plus longue (venue du fichier1.txt).
On peut améliorer mais ça donne des idées.

[MrPchoun]

Bonjour

Merci ! En fait j'arrive déjà à faire ce que tu me proposes, le principe d'isoler les substrings en commun jusque là c'est assez simple (ne te vexe pas !) La difficulté est d'aller plus loin, et de traiter ce qu'output ta fonction.

Par exemple je ne sais pas si ton algo donnera le même résultat pour (str1 = "200200" et str2 = "200") et (str1 = "200" et str2 = "200200") ?

En fait j’insiste vraiment sur ma nécessité de trouver sur mon graphe un algo pour isoler l'ensemble des cases violettes, une par axe. Ca irait plus droit au but, non ?

Ce n'est limite plus un problème de strings (dis donc ! ) (oui mauvaise blague ) mais plus un problème de graphe..

Voici ce à quoi je suis parvenu jusque là, exemple pour 8 graphes théoriques (je n'ai pas mis les strings) :
J'ai mis les strings similaires > 1 caractère en vert, et le résultat attendu en violet



Pour chaque graphe,
strings : somme des longueurs des strings trouvées
plus grand commun : je reporte en marge de chaque axe le nb de cases vertes ou vertes devenues violettes), -1. Je retiens finalement la plus grande somme, de l'axe X ou Y
résultat : la différence des deux, soit le nb de cases violettes. (c'est surtout cette donnée que je cherche à avoir, mais connaitre les substrings identifiées m'intéresse aussi)

Mais ça ne marche pas toujours (encarts oranges)

(pardon pour les images attachées en fin de message, je n'arrive pas à les supprimer..)

[Flodelarab]

En fait j'arrive déjà à faire ce que tu me proposes

À ceci près que tu as 4 correspondances sur ton schéma, alors qu'il y en a 11.

je ne sais pas si ton algo donnera le même résultat

Vois par toi-même :

Code :

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

1
2
3
4
5
6
7
8
9
10
200
200
00
0
00
00
0
0
0
0

Code :

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

1
2
3
4
5
6
7
8
9
10
200
00
00
0
0
200
00
00
0
0

Ca irait plus droit au but, non ?

Non.

J'ai mis les strings similaires > 1 caractère en vert, et le résultat attendu en violet

Dans mon code, la longueur de la correspondance est la variable "c". Si tu ne veux garder que le "c" maximum, tu peux. Tu peux même garder toutes les chaînes de longueur maximum.

Mais ça ne marche pas toujours (encarts oranges)

Oui. La règle que tu appliques n'existe pas. As-tu une preuve mathématique de cette idée ?

[anapurna]

salut

tout ceci s'apparente a la recherche de motif
il existe une multitude d’algorithme de recherche

[BufferBob]

salut,

étant donné qu'il n'y a pas de maxLength et qu'on souhaite éviter le recouvrement, de manière très pratique je partirai sur un algo type LCS que je ferai tourner jusqu'à épuisement des solutions ou que la substring retournée soit de taille inférieure à minLength