Bound Exception in algorithm of the longest common subsequence

Question

I wrote an algorithm which finds the longest common subsequence of two strings.

Here is what "plik1" file includes:

1 11 23 1 18 9 15 23 5
11 1 18 1 20 5 11 1

And here is what should save in file2:

11 1 18 5

After compiling there is an error:

String 1 : [1, 11, 23, 1, 18, 9, 15, 23, 5]
String 2 : [11, 1, 18, 1, 20, 5, 11, 1]

0 0 0 0 0 0 0 0 0 0 
0 0 1 1 1 1 1 1 1 1 
0 1 1 1 2 2 2 2 2 2 
0 1 1 1 2 3 3 3 3 3 
0 1 1 1 2 3 3 3 3 3 
0 1 1 1 2 3 3 3 3 3 
0 1 1 1 2 3 3 3 3 4 
0 1 2 2 2 3 3 3 3 4 
0 1 2 2 3 3 3 3 3 4 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10
    at Zadanie1.main(Zadanie1.java:74)

I have no idea, what is wrong with the code...

import java.io.*;
import java.util.ArrayList;
import java.util.Scanner;

public class Zadanie1 { 
    public static void main(String[] args) throws Exception {   

    Scanner file1 = new Scanner( new File("plik1.txt") );

    ArrayList<Integer> line1 = new ArrayList<Integer>();
    ArrayList<Integer> line2 = new ArrayList<Integer>();

    Scanner scan = new Scanner(file1.nextLine());
    while (scan.hasNext()){
        line1.add(scan.nextInt());
    }

    scan = new Scanner(file1.nextLine());
    while (scan.hasNext()){
        line2.add(scan.nextInt());
    }

    System.out.println("String 1 : " + line1);
    System.out.println("String 2 : " + line2);

     int[][] table = new int[line1.size()+1][line2.size()+1];

        StringBuffer subsequence = new StringBuffer();

            for (int i = 0; i<=line1.size(); i++) 
                table[i][0] = 0;

            for(int i = 0; i<=line2.size(); i++)
                table[0][i] = 0;

        for(int i = 1; i<=line1.size(); i++) {
            for (int j = 1; j<=line2.size(); j++) {

                if ( line1.get(i-1) == line2.get(j-1) )
                    table[i][j] = table[i-1][j-1] + 1;                  

                else
                    table[i][j] = Math.max(table[i-1][j], table[i][j-1]);

            }
        }

        for(int i=0; i<=line2.size(); i++) {
            System.out.println();
            for(int j=0; j<=line1.size(); j++) {
                System.out.print(table[j][i] + " ");
            }
        }


        for(int x = line1.size()+1, y = line2.size()+1, l1 = line1.size()-1, l2 = line2.size()-1; x != 0 && y != 0;
                l1--, l2--) {

            if( line1.get(l1) != line2.get(l2) ) {
                if( table[x][y-1] > table[x-1][y] ) y--;
                else if( table[x-1][y] > table[x][y-1]) x--;
            }

            else if( line1.get(l1) == line2.get(l2) ) {
                subsequence.append(line1.get(l1-1));
                x--; y--; 
            }
        }

       String buff = subsequence.reverse().toString();

    System.out.print("PO: " + buff);
    System.out.println();

    PrintWriter file2 = new PrintWriter("plik2.txt");

    file2.println(buff);
    file1.close();
    file2.close();
    }
}

Answer 1

I changed the code a bit:

    for(int x = line1.size()+1, y = line2.size()+1, l1 = line1.size()-1, l2 = line2.size()-1; x != 0 && y != 0;
            l1--, l2--) {

        if( line1.get(l1) != line2.get(l2) ) {
            if( table[x-1][y-2] > table[x-2][y-1] ) y--;
            else if( table[x-2][y-1] > table[x-1][y-2]) x--;
        }

        else if( line1.get(l1) == line2.get(l2) ) {
            subsequence.append(line1.get(l1-1));
            x--; y--; 
        }
    }

But there is still a problem. I know where, when function is calling e.g table[x-2][y-1] and x is 1, its bound of exception. I know I have to add an condition somewhere, but where and which ... I tried to add "if ((y-2 <0) || (x-2<0) ) break;" after "if( line1.get(l1) != line2.get(l2) )", but the compiler still says:

String 1 : [1, 11, 23, 1, 18, 9, 15, 23, 5]
String 2 : [11, 1, 18, 1, 20, 5, 11, 1]


0 0 0 0 0 0 0 0 0 0 
0 0 1 1 1 1 1 1 1 1 
0 1 1 1 2 2 2 2 2 2 
0 1 1 1 2 3 3 3 3 3 
0 1 1 1 2 3 3 3 3 3 
0 1 1 1 2 3 3 3 3 3 
0 1 1 1 2 3 3 3 3 4 
0 1 2 2 2 3 3 3 3 4 
0 1 2 2 3 3 3 3 3 4 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
    at java.util.ArrayList.elementData(Unknown Source)
    at java.util.ArrayList.get(Unknown Source)
    at Zadanie1.main(Zadanie1.java:73)

*EDIT: I added

for(int x = line1.size()+1, y = line2.size()+1, l1 = line1.size()-1, l2 = line2.size()-1; x != 1 && y != 1 && **l1 < 0 && l2 < 0;**
                l1--, l2--) {

Now, everything compiles properly, but there is no subsequence finded...

Answer 2

Based on the contents of the question, I am not sure where the NPE actually occurs but you created an array such as

 int[][] table = new int[line1.size()+1][line2.size()+1];

and then you try to access:

int x = line1.size()+1
table[x][y-1]

which looks suspicious