Trouver le maximum de substrings communes à deux strings, sans répétition

Version imprimable

22/03/2021, 19h11
MrPchoun

1 pièce(s) jointe(s)

Trouver le maximum de substrings communes à deux strings, sans répétition

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" :

Pièce jointe 594045

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 8O 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 ?

Bonjour :coucou:

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

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.

23/03/2021, 19h10
MrPchoun

3 pièce(s) jointe(s)

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 ! 8O) (oui mauvaise blague :oops:) 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

Pièce jointe 594151

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..)
23/03/2021, 22h32
Flodelarab
Citation:

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.

Citation:

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

Vois par toi-même :
Code:

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

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

Ca irait plus droit au but, non ?

Non.

Citation:

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.

Citation:

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 ?
24/03/2021, 10h05
anapurna

salut

tout ceci s'apparente a la recherche de motif
il existe une multitude d’algorithme de recherche
24/03/2021, 19h17
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
26/03/2021, 22h59
MrPchoun

2 pièce(s) jointe(s)

Bonsoir :mrgreen:

Merci pour toutes vos réponses !

@BufferBob : oui mais non :)

Prenons ces deux strings :

Pièce jointe 594400

La première LCS trouvée serait une chaine de 4 chars, et après il en trouverait une de 2, soit 6 chars en commn. Mais ici, pour maximiser le nombre de sous chaines trouvées (7 chars partagée pour des sous séquences d'au moins 2 chars), j'ai tout intérêt à les découper (pour un minLength de 2 dans ce cas là)

@anapurna : genre suffix tree ou prefix tree ? Pourrais-tu aller plus loin ?

@Floredelarab : ok, mettons que je parte avec ces données que tu sors, c'est à dire l'intégralité des sous séquences partagées par mes deux strings, sans tenir compte des recouvrements. Dans le nouvel exemple que j'ai mis plus haut, comment isoles-tu les substrings que j'ai dessiné en violet ? Attention il y a un piège :mouarf: "ab" est présent deux fois dans les deux strings mais c'est un résultat qui est cohérent. Formulé autrement, je pense vraiment que j'ai plutôt besoin de trouver un algo qui maximisera le nombre de cases verts à colorier en violet, tout en respectant le fait qu'il ne doit y avoir qu'une case violette par axe :calim2: Ce n'est pour le plaisir de te contredire, c'est qu'à partir du début de solution que tu me proposes je n'arrive pas à aller au bout de mon objectif.

Sinon j'avais trouvé un vidéo intéressante sur un algo LCS, au sens "longest common subsequence" et pas "longest common substring" (apparemment il y a une différence). Voilà le principe : https://www.google.fr/search?q=longe...8K0T7uBaGKIauM
Mais le hic c'est que déjà, il accepte les séquences de 1 caractère, et qu'en plus, j'ai l'impression que pour être détectables via cet algo, les séquences doivent être dans le même ordre dans string1 et dans string2. Ce qui n'est pas forcément le cas dans les données que je dois traiter..

Ne toujours pas tenir compte de l'image attachée :D
27/03/2021, 01h08
Flodelarab

Ah. Je viens juste de comprendre l'énoncé. Je ne vois, a priori, pas d'autre façon que de faire tous les cas possibles. J'ai une méthode en tête, mais je ne vais pas tester maintenant.
27/03/2021, 08h55
BufferBob

Citation:

Envoyé par Flodelarab

Ah. Je viens juste de comprendre l'énoncé.

pareil, j'avais pas fait attention que le but était de maximiser le nombre de substrings

mais je serais tenté de rester sur la même approche (même si elle n'est probablement pas optimale) ; faire tourner LCS et à la fin diviser les chaines en chunks de minLength éléments (du coup une substring commune "abdef" avec minLength=2 renverrait 'ab' et 'cde', c'est bien l'idée ?)

Proposition :

Code:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#!/usr/bin/awk -f
 
function retrouver_mots()
{
	delete prec;
	delete suiv;
	delete mots;
	nbmots=0;
 
	for (i in v) {
		suiv[(x[v[i]]-1)"M"(y[v[i]]-1)]=i;
		prec[(x[v[i]]+1)"M"(y[v[i]]+1)]=i;
		}
	for (i in v)
		if (prec[(x[v[i]])"M"(y[v[i]])]=="")
		{
			pos=i
			nbmots++;
			while (pos!="") {
				mots[nbmots]=mots[nbmots]$(x[v[pos]])
				pos=suiv[(x[v[pos]])"M"(y[v[pos]])]
			}
		}
 
	tl=0
	for (im in mots) {
		l=length(mots[im]);
		if (l<2) {
			delete mots;
			return;
		}
		tl+=l;
	}
 
	if (tl>max) {
		max=tl
		for (i=1;i<=nbmots;i++)
			mem[i]=mots[i];
	}
 
}
 
FNR==NR{
	for (i=1;i<=NF;i++) {
		tab[i]=$i;l1++;
	} 
	next;
} 
 
{
	for (i=1;i<=NF;i++) 
		for (j=1;j<=l1;j++) 
			if (tab[j]==$i) {
				n++;
				x[n]=i;
				y[n]=j;
			}; 
	c=1; 
	while (c>0) {
		if ((lx[x[c]]==0)&&(ly[y[c]]==0)) {
			lx[x[c]]=1; 
			ly[y[c]]=1; 
			nv++; 
			v[nv]=c;
		} 
 
		c++;
		# retour en arrière
		while (c>n) {
			if (nv>=max) {
				retrouver_mots();
			}			
			delete lx[x[v[nv]]];
			delete ly[y[v[nv]]];
			c=v[nv]+1;
			delete v[nv];
			nv--;
			if (nv<0)
				c=-1
		}
	}; 
}
 
END{
	print max,"correspondances";
	for (i in mem)
		print mem[i];
}

Résultat :

Code:

1
2
3
4
5
6
7
8
9
10
11
Avec 'abcdbcde' et 'abcdeab', on obtient 6 correspondances
bcde
ab
 
Avec '200200' et '200', on obtient 3 correspondances
200
 
Avec 'abcdabbcde' et 'abcdeab', on obtient 7 correspondances
abc
de
ab

Mais je ferais remarquer que pour 7 correspondances, on peut avoir, par exemple, les répartitions suivantes : 2/2/3 ou 4/3 ou 5/2. Ce qui n'est pas la même chose. Il va falloir trancher.

27/03/2021, 12h31
MrPchoun

C'est du génie 8O8O8O

Je vais adapter ton code sur mon langage et voir comment je peux en sortir mes substrings. Mais déjà tu as fait un travail de fou, c'est de me sortir le nombre de chars communs, et c'est l'info primaire dont j'ai besoin pour comparer mes strings.

Merci beaucoup à toi, je m'en vais me plonger dans ton script !

Reconnaissance éternelle 8-)

Bonjour :salut:

Déterrage :)

Je me rends compte que ton script ne fonctionne pas avec les valeurs "60d020252pce" et "2526" (attendu "252").

J'aimerais arriver à débugger moi même, mais n'étant pas un habitué de awk j'ai traduit en c++ :

Code:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <iostream> 
#include <cmath>
#include <map>
#include <vector>
#include <algorithm>
 
std::string STR1;
std::string STR2;
 
 
 
typedef std::pair<int,int> Pair;
 
int x[1000] = {0};
int y[1000] = {0};
int lx[1000] = {0};
int ly[1000] = {0};
int v[1000] = {0};
int nv = 0;
 
int max = 0;
 
void retrouver_mots() {
 
    std::map<Pair,int> suiv;
    std::map<Pair,int> prec;
    std::vector<std::string> mots;
 
    // ici, les valeurs ne v ne s'affichent pas dans le même ordre en awk et en c++
    for (int k=1; k<=nv; k++) {
        int i = v[k];
        suiv[Pair((x[v[i]]-1),(y[v[i]]-1))] = i;
        prec[Pair((x[v[i]]+1),(y[v[i]]+1))] = i;
    }
 
 
    for (int k=1; k<=nv; k++) {
 
        int i = v[k];
 
        if (prec[Pair((x[v[i]]),(y[v[i]]))] == 0)
        {
            int pos = i;
 
            std::string mot = "";
 
            while (pos != 0) {
 
                mot = mot + STR1[x[v[pos]]];
 
                pos = suiv[Pair((x[v[pos]]),(y[v[pos]]))];
            }
 
            mots.push_back(mot);
        }
    }
 
    int tl = 0;
 
    for (int k=0; k<mots.size(); k++) {
        int l = mots[k].length();
        if (l<2) {
            return;
        }
        tl+=l;
    }
 
 
    if (tl > max) {
        max = tl;
        for (int i=0; i<mots.size(); i++)
            std::cout << mots[i] << std::endl;
    }
 
}
 
void correspondances(std::string str1, std::string str2) 
{
    STR1 = str1;
    STR2 = str2;
 
    int n=0;
 
    for (int i=0; i<str1.length(); i++) 
        for (int j=0; j<str2.length(); j++) 
            if (str1[i] == str2[j]) {
                n++;
                x[n]=i;
                y[n]=j;
            }; 
 
    int c = 1;
 
    while (c > 0) {
 
        if (lx[x[c]]==0 && ly[y[c]]==0) {
            lx[x[c]]=1; 
            ly[y[c]]=1; 
            nv++; 
            v[nv]=c;
        } 
 
        c++;
 
        while (c > n) {
 
            if (nv >= max) 
                retrouver_mots();
 
            lx[x[v[nv]]] = 0;
            ly[y[v[nv]]] = 0;
            c=v[nv]+1;
            v[nv]=0;
            nv--;
            if (nv<0)
                c=-1;
        }
 
 
    }
 
    std::cout << max << " coresspiondances";
}

Évidement ce n'est pas idéal, variables globales etc, mais c'était pour comprendre l'algo. Or cette traduction c++ ne fonctionne pas non plus. J'attribue ce dysfonctionnement aux lignes 30 et 37 : a priori (for i in v) et (for k=1; k<=nv; k++ // v[k]) ne produisent pas les résultats dans le même ordre, et je suspecte que le bug vienne de là.

Pourrais-tu éventuellement traduire ton script dans un pseudo code un peu plus haut niveau, plus facilement compréhensible, et donc plus facilement modifiable pour moi ?

J'ai l'impression d'être relou, pardon :mrgreen:

01/04/2021, 18h21
Flodelarab
J'avoue que c'est rude de poster mon code avec des variables mono-lettre et sans explications. Si tu as des questions n'hésite pas. Sur les variables comme sur le procédé, ou sur awk.

J'ai essayé mon algo sur des lignes de fichier texte plus longues que ces petites expressions, et la quantité de mots de 1 lettre est trop important. C'est trop long. Il faudrait refaire l'algo plus orienté sur les mots qui s'excluent les un les autres. Mais comme tu avais l'air content, je n'ai pas creusé.

Enfin, pour ce qui concerne le fonctionnement, le cas que tu donnes marche chez moi :
Code:

1 2 Avec '60d020252pces' et '2526', on obtient 3 correspondances 252

Citation:

Enfin, pour ce qui concerne le fonctionnement, le cas que tu donnes marche chez moi :

Alors c'est moi :)

En fait je dois utiliser cette fonction sur un serveur, via le php je peux appeler un shell avec le script awk.

Quelles seraient les différences entre ta version et celle ci ? (car celle ci ne produit aucun résultat)
Code:

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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 function retrouver_mots() { delete prec; delete suiv; delete mots; nbmots=0; for (i in v) { suiv[(x[v[i]]-1)"-"(y[v[i]]-1)]=i; prec[(x[v[i]]+1)"-"(y[v[i]]+1)]=i; } for (i in v) if (prec[(x[v[i]])"-"(y[v[i]])]=="") { pos=i nbmots++; while (pos!="") { mots[nbmots]=mots[nbmots](substr(strings[0], x[v[pos]]+1, 1)) pos=suiv[(x[v[pos]])"-"(y[v[pos]])] } } tl=0 for (im in mots) { l=length(mots[im]); if (l<2) { delete mots; return; } tl+=l; } if (tl>max) { max=tl for (i=1;i<=nbmots;i++) print mots[i]; } } BEGIN { strings[0] = "60d020252pce"; strings[1] = "2526"; for (i=0; i<length(strings[0]); i++) { for (j=0; j<length(strings[1]); j++) { if (substr(strings[0], i+1, 1) == substr(strings[1], j+1, 1)) { n++; x[n]=i; y[n]=j; } } } c=1; while (c>0) { if ((lx[x[c]]==0)&&(ly[y[c]]==0)) { lx[x[c]]=1; ly[y[c]]=1; nv++; v[nv]=c; } c++; while (c>n) { if (nv>=max) retrouver_mots(); lx[x[v[nv]]] = 0; ly[y[v[nv]]] = 0; c=v[nv]+1; v[nv] = 0; nv--; if (nv<0) c=-1 } }; print max,"correspondances"; }
De ce que je comprends, ton algo commence par une liste des matchs de char, et du stockes dans x et dans y la position de ces chars dans str1 et dans str2, non ? Je pensais faire pareil mais a priori non, je n'ai modifié que ça :)

Je cherche juste à éviter la création de fichiers, plus couteuse en temps que d'appeler directement le script avec les valeurs des strings.

01/04/2021, 18h58
Flodelarab

Glossaire :

function retrouver_mots() --> fonction, à la fin, qui reconstitue les mots à partir des cases violettes.

function retrouver_mots()
FNR==NR{next;}
{}
END{}
--> on définit une fonction. Le second bloc est fait sur le premier fichier, le troisième bloc sur le second fichier, et le quatrième bloc END est fait en guise de conclusion.

tableau[] --> attention ! La plupart du temps, ce sont des tableaux associatifs (indice en chaîne de caractères), et non des tableaux indexés (indices en nombre) comme en c++.
prec --> tableau des précédents.
suiv --> tableau des suivants.
mots --> tableau des mots identifiés à partir des cases violettes
nbmots --> nombre de mots identifiés
v --> tableau des cases violettes
i --> n'importe quel indice locale :)
x --> tableau des positions de la lettre dans un mot. Soit l'abscisse.
y --> tableau des positions de la lettre dans l'autre mot. Soit l'ordonnée.
"M" --> séparateur artificiel pour éviter que "1" et "12" donne le même indice que "11" et "2". "1M12", "11M2".
pos --> curseur local pour désigner l'indice de la lettre du mot en train de s'écrire.
tl --> total length = longueur total = nombre de correspondances pour ce cas
im --> indice de mot pareil à "i" mais appliqué à "mots"
l --> longueur du mot à l'étude
max --> nombre de correspondances maximal. Le graal.
mem --> mémoire des mots pour lesquels la correspondance est maximale.
FNR --> variable awk. Nombre de ligne du fichier
NR --> variable awk. Nombre de ligne total. Quand ces 2 dernières variables sont égales, on est dans le premier fichier.
NF --> variable awk. Nombre de lettres de la ligne.
l1 --> longueur de la chaîne de caractères du fichier 1.
tab --> tableau mémoire de ce qu'il y avait dans le premier fichier. La première chaîne.
j --> indice. Même combat que i.
n --> nombre de coïncidences. Une lettre de la première chaîne est identique à une lettre de la deuxième chaîne.
c --> curseur. On va passer en revue toutes les lettres vertes (en coïncidence)
lx --> tableau disant si la colonne x est libre d'utilisation.
ly --> tableau disant si la ligne y est libre d'utilisation.
nv --> nombre de violets.

En résumé, on colorie en vert, puis en violet, puis on retrouve les mots avec les cases violettes.

Merci !! Et voici le code final :mrgreen:

Code:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
<?php
    $str1 = $_GET['str1'];
    $str1 = $_GET['str2'];
    $shell = 'function retrouver_mots()
    {
    	delete prec;
    	delete suiv;
    	delete mots;
    	nbmots=0;
     
    	for (i in v) {
    		suiv[(x[v[i]]-1)"M"(y[v[i]]-1)]=i;
    		prec[(x[v[i]]+1)"M"(y[v[i]]+1)]=i;
    	}
    	
    	for (i in v)
    		if (prec[(x[v[i]])"M"(y[v[i]])]=="")
    		{
    			pos=i
    			nbmots++;
    			while (pos!="") {
    				mots[nbmots]=mots[nbmots](substr(strings[0], x[v[pos]]+1, 1))
    				pos=suiv[(x[v[pos]])"M"(y[v[pos]])]
    			}
    		}
     
    	tl=0
    	for (im in mots) {
    		l=length(mots[im]);
    		if (l<2) {
    			delete mots;
    			return;
    		}
    		tl+=l;
    	}
     
    	if (tl>max) {
    		max=tl
    		for (i=1;i<=nbmots;i++)
    			mem[i]=mots[i];
    	}
     
    }
     
    BEGIN {
    
    	strings[0] = "' . $_GET['str1']. '";
       	strings[1] = "' . $_GET['str2']. '";
    
    	for (i=0; i<length(strings[0]); i++) {
    		for (j=0; j<length(strings[1]); j++) {
    			if (substr(strings[0], i+1, 1) == substr(strings[1], j+1, 1)) {
          			n++;
    				x[n]=i;
    				y[n]=j;
          		}
    		}
    	}
    
    	c=1; 
    	while (c>0) {
    		if ((lx[x[c]]==0)&&(ly[y[c]]==0)) {
    			lx[x[c]]=1; 
    			ly[y[c]]=1; 
    			nv++; 
    			v[nv]=c;
    		} 
     
    		c++;
    
    		while (c>n) {
    			if (nv>=max) {
    				retrouver_mots();
    			}			
    			delete lx[x[v[nv]]];
    			delete ly[y[v[nv]]];
    			c=v[nv]+1;
    			delete v[nv];
    			nv--;
    			if (nv<0)
    				c=-1
    		}
    	}; 
    }
    
    END {
    	for (i in mem)
    		print mem[i];
    }';
 
    $output = shell_exec("awk '" . $shell . "'");
    $output = substr($output, 0, -1);
    $output = explode("\n", $output);
    echo json_encode($output);
?>

Citation:

J'ai essayé mon algo sur des lignes de fichier texte plus longues que ces petites expressions, et la quantité de mots de 1 lettre est trop important. C'est trop long. Il faudrait refaire l'algo plus orienté sur les mots qui s'excluent les un les autres. Mais comme tu avais l'air content, je n'ai pas creusé.

Ou peut-être tout simplement en allant chercher quelque chose du style :

Code:

if (tab[j]==$i && tab[j+1]==$i+1)

A creuser, mais je ne fais que comparer des strings de max 30 chars chacune, pour l'instant ça fait très largement le taff.

Rerésolu, merci à toi Flodelarab !!

Et pour le même prix voici la traduction javascript 8-)

Code:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
function commonSubstrings(str1, str2) {
 
                let x = [];
                let y = [];
                let v = [];
                let colonne = [];
                let ligne = [];
                let mem = [];
 
                for (let i=0; i<str1.length; i++) 
                    for (let j=0; j<str2.length; j++) 
                        if (str1[i] == str2[j] && (str1[i+1] == str2[j+1] || str1[i-1] == str2[j-1])) {
                            x.push(i);
                            y.push(j);
                        }; 
 
                for (let i=0; i<str1.length; i++) 
                    colonne.push(0);
                for (let j=0; j<str2.length; j++) 
                    ligne.push(0);
 
                let max = 0;
                let c = 0;
 
                while (c >= 0) {
 
                    if (colonne[x[c]] == 0 && ligne[y[c]] == 0) {
                        colonne[x[c]] = 1; 
                        ligne[y[c]] = 1; 
                        v.push(c);
                    } 
 
                    c++;
 
                    while (c > x.length) {
 
                        if (v.length == 0)
 
                            c = -1;
 
                        else {
 
                            if (v.length >= max) {
 
                                let mots = [];
                                let suiv = [];
                                let prec = [];
 
                                for (let i=0; i<v.length; i++) {
                                    suiv[[x[v[i]]-1,y[v[i]]-1]] = i+1;
                                    prec[[x[v[i]]+1,y[v[i]]+1]] = i+1;
                                }
 
                                for (let i=0; i<v.length; i++) {
 
                                    if (prec[[x[v[i]],y[v[i]]]] == null)
                                    {
                                        let pos = i+1;
 
                                        mots.push('');
 
                                        while (true) {
 
                                            mots[mots.length-1] += str1[x[v[pos-1]]];
 
                                            if (suiv[[x[v[pos-1]],y[v[pos-1]]]] != null)
                                                pos = suiv[[x[v[pos-1]],y[v[pos-1]]]];
                                            else
                                                break;
                                        }
                                    }
                                }            
 
                                let totalLength = 0;
 
                                for (let k=0; k<mots.length; k++) {
                                    let length = mots[k].length;
                                    if (length < 2) {
                                        totalLength = 0;
                                        break;
                                    }
                                    totalLength += length;
                                }
 
                                if (totalLength > max) {
                                    max = totalLength;
                                    mem = mots;
                                }
                            }
 
                            colonne[x[v[v.length-1]]] = 0;
                            ligne[y[v[v.length-1]]] = 0;
                            c = v[v.length-1] + 1;
                            v.pop();
                        }
                    }
                }
 
                for (let i=0; i<mem.length; i++)
                    console.log(mem[i]);
 
            }
 
            commonSubstrings('oo39quaidemarnecs40197i', 'insertth162026coffretvirax990019');