Найти наибольшую общую подпоследовательность

Question

У меня есть следующий код, который по какой-то причине, который я пытаюсь выяснить, работает неправильно:

public static int score(String gene1, String gene2){
    char[] a=new char[gene1.length()];
    char[] b=new char[gene2.length()];
    a=gene1.toCharArray();
    b=gene2.toCharArray();
    return score(a, b, 0,0);
}

private static int score(char[] a, char[] b, int i, int j){
    if(a[i]=='\0' || b[j]=='\0')
        return 0;
    else if (a[i]==b[j])
        return 1+score(a, b, i+1, j+1);
    else 
        return max(score(a, b,i+1, j),score(a, b, i, j+1));
}

private static int max (int a, int b){
    if (a<b) return b;
    else return a;
}

Вот где это терпит неудачу:

assertEquals(2, GeneAnalysis.score("ACGT","AC")); 

Я получаю ошибку IndexOutofBoundsError

Есть идеи? Также, предлагая помощь, не меняйте параметры метода. Они должны быть такими, какие они есть.

Answer 1

Частично это похоже на путаницу между C и Java ....

if(a[i]=='\0' || b[j]=='\0')
        return 0;

C имеет нулевой терминатор для строк, Java - нет. Вместо этого, чтобы проверить конец массива Java, вам нужно использовать атрибут .length ... что-то вроде:

   if(i >= a.length || j >= b.length) 

Редактировать на основе комментария.

На самом деле, вам следует задать отдельный вопрос по этому вопросу ... но вот пример того, как это работает. Во-первых, вы используете рекурсию, которая, да, является хитрой концепцией. Википедия, вероятно, может помочь вам с основами рекурсии.

Вот код ближе к тому, как я написал бы, с комментариями, показывающими вам порядок, в котором происходят вещи:

public class Main
{
    public static void main(String[] args)
    {
        final int value;

        value = score("ACGT", "AC");
        System.out.println(value);
    }

    public static int score(final String gene1,
                            final String gene2)
    {
        final char[] a;
        final char[] b;
        final int    s;

        a = gene1.toCharArray();
        b = gene2.toCharArray();
        s = score(a, b, 0, 0);

        return (s);
    }

    private static int score(final char[] a,
                             final char[] b,
                             final int    idxA,
                             final int    idxB)
    {
        final int value;

        // for all calls: a.length == 4 and b.length == 2
        // first call:  idxA == 0 and idxB == 0 - false || false == false
        // second call: idxA == 1 and idxB == 1 - false || false == false
        // third call:  idxA == 2 and idxB == 2 - false || true  == true      
        if(idxA >= a.length || idxB >= b.length)
        {
            // third call: will return 0            
            value = 0;
        }
        // first call:  a[idxA] == A and b[idxB] == A - true
        // second call: a[idxB] == C and b[idxB] == C - true 
        else if(a[idxA] == b[idxB])
        {
            // this is recursion
            // first call:  1 + score(a, b, 1, 1)
            // second call: 1 + score(a, b, 2, 2)

            // after the third call the call stack starts unwinding
            // second call: 1 + 0 == 1
            // first call:  1 + 1 == 2
            value = 1 + score(a, b, idxA + 1, idxB + 1);
        }
        else
        {
            final int x;
            final int y;

            x = score(a, b, idxA + 1, idxB);
            y = score(a, b, idxB,     idxB + 1);
            value = max(x, y);
        }

        // third call:  0
        // second call: 1
        // first call:  2
        return (value);
    }

    // Can you use Math.max(int, int) instad?
    private static int max(final int x, final int y)
    {
        final int value;

        if(x < y)
        {
            value = y;
        }
        else
        {
            value = x;
        }

        return (value);
    }
}

Answer 2

public static int score(String gene1, String gene2){
    char[] a=gene1.toCharArray();//assign it directly
    char[] b=gene2.toCharArray();
    return score(a, b, 0, 0);
}

private static int score(char[] a, char[] b, int i, int j) {
    //check for end using length, java doesn't use that nullbyte-stuff for it
    //this caused the failure
    if(i==a.length || j==b.length) {
        return 0;
    } else if (a[i]==b[j]) {
        return 1+score(a, b, i+1, j+1);
    } else {
        return max(score(a, b, i+1, j), score(a, b, i, j+1));
    }
}

private static int max (int a, int b){
    if (a<b) return b;
    return a;
}

Answer 3

char[] a=new char[gene1.length()];
a=gene1.toCharArray();

Хм. Что происходит с массивом, выделенным в первой строке?