Inverser l'affichage de ma fontion

Version imprimable

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:

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("");
 
    }

27/02/2013, 02h32
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:

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.
27/02/2013, 03h00
metraon
A vrai dire j'aimerais obtenir
Code:

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
27/02/2013, 04h46
Sharcoux

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

Dans ce cas, regarde cette ligne :

Code:

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

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
    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("");
 
    }