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

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:

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

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

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

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 ;].