java - 最长公共(public)子序列算法中的绑定(bind)异常

Question

我编写了一个算法，可以找到两个字符串的最长公共(public)子序列。

以下是“plik1”文件的内容:

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

这是应该保存在 file2 中的内容:

11 1 18 5

编译后出现错误:

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)

我不知道代码有什么问题......

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

根据问题的内容，我不确定 NPE 实际发生在哪里，但您创建了一个数组，例如

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

然后您尝试访问:

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

看起来很可疑