(java) Najdłuższy wspólny podciąg - złe wyniki

0

Witam. Bawię się sobie różnymi algorytmami i natrafiłem na problem. Chcę wypełnić tabelkę tak jest to pokazane tutaj http://pl.wikipedia.org/wiki/Nwp#Algorytm_odtwarzaj.C4.85cy_NWP . Problem w tym że po wypełnieniu tabelki wygląda ona tak:

user image

Co robię źle? Kod:

import java.io.IOException;
public class Testy 
{
    public static void main(String[] args) throws IOException 
    {
        String A = "babab";
        String B = "abaabbaaa";

        int n = A.length()+1;
        int m = B.length()+1;

        int[][] C = new int[n][m];      

        for (int i=1;i<n;i++)
        {
            for (int j=1;j<m;j++)
            {
                if (A.charAt(i-1) == B.charAt(j-1))
                    C[i][j] = C[i-i][j-1]+1;
                else
                    C[i][j] = Math.max(C[i-1][j], C[i][j-1]);
            }
        }

        ///////// kod wyswietlajacy tabelke, brzydki ale pisany na szybko /////////////

        // wyswietl znaki ciagu 'abaabbaaa'
        System.out.print("    ");
        for(int i=0;i<B.length();i++)
            System.out.print(B.charAt(i)+" ");
        System.out.print("\n  ");
        //////

        int znak_A=0;
        for (int i=0;i<n;i++)
        {
            for (int j=0;j<m;j++)
            {
                if (i==0) // jesli to pierwszy wiersz to wyswietl same zera
                    System.out.print(C[i][j]+" ");
                else if (j==0) // jesli to pierwsza kolumna to wyswietl znak o indeksie znak_A, ciagu 'babab' oraz zero
                {
                    System.out.print(A.charAt(znak_A)+" "+C[i][j]+" ");
                    znak_A++; // nastepny element ciagu 'babab'
                }
                else // dla pozostalych elementow tabeli
                    System.out.print(C[i][j]+" ");
            }
            System.out.println();
        }
    }
}
0

Nie mam nic do Javy chwilowo zainstalowanego, więc napisałem w C# i dla niepoznaki zrobiłem javowe klamerki (których Ty btw. nie stosujesz) ;).

string a = "babab";
string b = "abaabbaaa";
int[,] lcs = new int[a.Length + 1, b.Length + 1];

for (int i = 0; i < a.Length; i++) {
    for (int j = 0; j < b.Length; j++) {
        if (a[i] == b[j]) { // tu się operator trójargumentowy narzuca, ale byłoby mniej czytelnie chyba
            lcs[i + 1, j + 1] = lcs[i, j] + 1;
        } else {
            lcs[i + 1, j + 1] = Math.Max(lcs[i + 1, j], lcs[i, j + 1]);
        }
    }
}

Do wypisania po prostu:

for (int i = 0; i < lcs.GetLength(0); i++) {
    for (int j = 0; j < lcs.GetLength(1); j++) {
        Console.Write("{0} ", lcs[i, j]);
    }
    Console.WriteLine();
}
Console.ReadKey(true);

Ok, ale teraz co jest u Ciebie źle?

if (A.charAt(i-1) == B.charAt(j-1))
    C[i][j] = C[i-i][j-1]+1;
else
    C[i][j] = Math.max(C[i-1][j], C[i][j-1]);

Popatrz na to dookładnie;].
A później pewnie doświadczysz drobnego załamania ;P

0

Aktualny kod:

class Testy 
{
    public static void main(String[] args) throws java.io.IOException 
    {
        String A = "babab";
        String B = "abaabbaaa";

        int n = A.length();
        int m = B.length();

        int[][] C = new int[n+1][m+1];

        for (int i=0;i<n;i++)
        {
            for (int j=0;j<m;j++)
            {
                if (A.charAt(i) == B.charAt(j))
                    C[i+1][j+1] = C[i][1] + 1;
                else
                    C[i+1][j+1] = Math.max(C[i+1][j], C[i][j+1]);
            }
        }

        for (int i=0;i<n+1;i++)
        {
            for (int j=0;j<m+1;j++)
                    System.out.print(C[i][j]+" ");
            System.out.println();
        }
    }
}

Teraz działa lepiej, aczkolwiek dalej niepoprawnie, bo brakuje numeru 4. Można to zobaczyć tutaj http://ideone.com/qiGNGR

A co do mojego kodu to ciągle wydaje mi się, że był poprawny. Przecież iteracja zaczynała się od 1, więc poza tablicę nie wychodziło.

Np. miałem sobie komórkę C[1][2]=1. Później gdy znaki się zgadzały, to było równanie C[2][3]=C[1][2]+1 i przy debugowaniu dalej wychodziło mi 1. Tak jakby jakimś cudem C[1][2] zmieniało wartość na 0. A tak w ogóle to swój kod opierałem na pseudokodzie z wikipedii, myslałem że z tym problemu nie będę miał :P

0

Akurat kwestia czy iterujemy 1..n+1 czy 0..n to mała różnica (ja wolałem to drugie bo tak mi się napisało, Ty pierwsze).

Widzę że dalej nie widzisz gdzie miałeś i masz błąd. Polecam kupić sobie okulary, bo męcząc się z literówkami daleko nie zajedziesz ;P

Stary kod:

 C[i][j] = C[i-i][j-1]+1;

C[i-i] -> i-i? i-i jest równe zero. Miało być oczywiście C[i-1][j-1] + 1

Nowy kod:

  C[i+1][j+1] = C[i][1] + 1;

C[i][1] -> C[i][1]? Miało być przecież C[i][j]...
http://ideone.com/cEBA3N

Poważnie, kup (mocniejsze) okulary ;].

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0