1

2 つの文字列の最長共通部分列を見つけるアルゴリズムを書きました。

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

2 に答える 2

1

質問の内容に基づいて、NPEが実際にどこで発生するかはわかりませんが、次のような配列を作成しました

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

次に、アクセスしようとします：

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

不審に見えるもの

于 2014-12-01T17:45:16.103 に答える
0

コードを少し変更しました：

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

しかし、まだ問題があります。関数が table[x-2][y-1] などを呼び出していて、x が 1 の場合、例外の境界がどこにあるかを知っています。どこかに条件を追加する必要があることはわかっていますが、どこに、どの...「if ((y-2 <0) || (x-2<0) ) break;」を追加しようとしました。「if( line1.get(l1) != line2.get(l2) )」の後、コンパイラはまだ言います：

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)

※追記：追記しました

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--) {

これで、すべてが適切にコンパイルされますが、サブシーケンスが見つかりません...

于 2014-12-01T18:10:39.353 に答える