Discussion :

[metraon]

Bonjour, j'ai une fonction qui fait partiellement ce que je veux. Elle est supposée aligner des chaines de charactères en place mais le tout est inversé, les charactères sont dans le mauvais ordre. J'ai asseyé en vain d'iverser les deux for avec des incrémenteurs positifs mais cela ne marche pas, qu'est-ce que j'ai manqué ?

Merci

Code :

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

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
    public static void main(String[] args) {
        new LCS().align("MKNLASREVNIYVNGKLV", "QMASREVNIYVNGKL");
 
    }
 
    public static void align(String a, String b) {
        int[][] T = new int[a.length() + 1][b.length() + 1];
 
        for (int i = 0; i <= a.length(); i++) {
            T[i][0] = i;
        }
 
        for (int i = 0; i <= b.length(); i++) {
            T[0][i] = i;
        }
 
        for (int i = 1; i <= a.length(); i++) {
            for (int j = 1; j <= b.length(); j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    T[i][j] = T[i - 1][j - 1];
                } else {
                    T[i][j] = Math.min(T[i - 1][j], T[i][j - 1]) + 1;
                }
            }
        }
 
        for (int i = a.length(), j = b.length(); i > 0 || j > 0;) {
            if (i > 0 && T[i][j] == T[i - 1][j] + 1) {
                --i;
                System.out.print('-');
            } else if (j > 0 && T[i][j] == T[i][j - 1] + 1) {
                System.out.print(b.charAt(--j));
            } else if (i > 0 && j > 0 && T[i][j] == T[i - 1][j - 1]) {
                --i;
                System.out.print(b.charAt(--j));
            }
 
        }
        System.out.println("");
 
        for (int i = a.length(), j = b.length(); i > 0 || j > 0;) {
            if (i > 0 && T[i][j] == T[i - 1][j] + 1) {
                System.out.print(a.charAt(--i));
            } else if (j > 0 && T[i][j] == T[i][j - 1] + 1) {
                --j;
                System.out.print('-');
            } else if (i > 0 && j > 0 && T[i][j] == T[i - 1][j - 1]) {
                --j;
                System.out.print(a.charAt(--i));
            }
        }   
        System.out.println("");
 
    }

[Sharcoux]

Tu peux nous expliquer ce que tu souhaites obtenir exactement, parce que pour moi c'est pas très clair...

Si je comprends bien, tu veux aligner les lettres identiques des deux mots passés en paramètre. Pour ça tu utilises un algorithme qui, j'avoue m'échappe un peu, mais ce n'est visiblement pas le sujet. Au final, moi j'obtiens ça :

Code :

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

1
2
3
 
-LKGNVYINVERSA---MQ
VLKGNVYINVERSALNKM-

ce qui me semble répondre au problème.

Tu dis que le résultat est à l'envers, j'ai du mal à voir par rapport à quoi vu que tu déplaces tes lettres. Malgré tout, rien ne t'empêche d'inverser tes chaines avec, par exemple, StringBuilder.reverse() ou autre.

[metraon]

A vrai dire j'aimerais obtenir

Code :

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

1
2
3
 
QM---ASREVNIYVNGKL-
-MKNLASREVNIYVNGKLV

J'utilise une déviation de Levenshtein et de Smith-Waterman. Mon code initial utilisait un StringBuilder, mais je dois le traduire en assembleur, donc j'asseye d'enlever les objets et les fonctions trop ''avancés'' de Java.

Si ce n'est pas possible d'inverser l'algorythme, je vais simplement faire une fonction pour inverser la source, ce n'est pas si grave.

Merci

[Sharcoux]

D'accord. J'avais pas compris. Je ne connaissais pas cet algorithme.

Dans ce cas, regarde cette ligne :

Code :

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

System.out.print(b.charAt(--j));

Tu parcours ta chaine de droite à gauche. Pas étonnant que le résultat soit inversé. Il faut que tu inverses tes boucles for d'écriture.

Le problème, c'est que, si j'ai bien compris ton algo, tu dois écrire ta chaine dans le sens inverse de celui dans lequel tu as créé ton tableau. Il faut donc inverser aussi le sens de création de T (commencer par remplir T[a.length()][i]() et T[i][b.length()], etc).

Bonne chance

[Sharcoux]

Code :

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

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
    public static void main(String[] args) {
        align("MKNLASREVNIYVNGKLV", "QMASREVNIYVNGKL");
    }
 
    public static void align(String a, String b) {
        int[][] T = new int[a.length() + 1][b.length() + 1];
 
        for (int i = 0; i <= a.length(); i++) {
            T[i][b.length()] = a.length()-i;
        }
 
        for (int i = 0; i <= b.length(); i++) {
            T[a.length()][i] = b.length()-i;
        }
 
        for (int i = a.length()-1; i >= 0; i--) {
            for (int j = b.length()-1; j >= 0; j--) {
                if (a.charAt(i) == b.charAt(j)) {
                    T[i][j] = T[i + 1][j + 1];
                } else {
                    T[i][j] = Math.min(T[i + 1][j], T[i][j + 1]) + 1;
                }
            }
        }
 
        for (int i = 0, j = 0; i < a.length() || j < b.length();) {
            if (i < a.length() && T[i][j] == T[i+1][j] + 1) {
                i++;
                System.out.print('-');
            } else if (j < b.length() && T[i][j] == T[i][j+1] + 1) {
                System.out.print(b.charAt(j++));
            } else if (i < a.length() && j < b.length() && T[i+1][j+1] == T[i][j]) {
                i++;
                System.out.print(b.charAt(j++));
            }
        }
        System.out.println("");
 
        for (int i = 0, j = 0; i < a.length() || j < b.length();) {
            if (i < a.length() && T[i][j] == T[i+1][j] + 1) {
                System.out.print(a.charAt(i++));
            } else if (j < b.length() && T[i][j] == T[i][j+1] + 1) {
                ++j;
                System.out.print('-');
            } else if (i < a.length() && j < b.length() && T[i+1][j+1] == T[i][j]) {
                ++j;
                System.out.print(a.charAt(i++));
            }
        }
        System.out.println("");
 
    }