Оптимизация проблемы рекурсивной длинной общей подстроки (LCS) - PullRequest
Новая
       17

Оптимизация проблемы рекурсивной длинной общей подстроки (LCS)

0 голосов
/ 28 ноября 2018

У меня есть следующий код на Java: 

public static int Secret(String a, String b, int x, int y){
    if ((x == -1) || (y == -1)) {
        return 0;
    }

    if (a.charAt(x) == b.charAt(y)) {
        return Secret(a, b, x-1, y-1) + 1;
    } else {
        int left = Secret(a, b, x, y-1);
        int up = Secret(a, b, x-1, y);

        if (left > up) {
            return left ;
        } else {
            return up;
        }
    }

    return -1; 
}

Этот код выглядит как самая длинная общая проблема с подстрокой, но со сложностью мусора.Я должен оптимизировать его до O (mn) (пространство и время).

Я пытался следовать алгоритму из Википедии (https://en.wikipedia.org/wiki/Longest_common_substring_problem),, то есть O (mn) (пространство и время).

public static int iterativeLCS(String a, String b, int x, int y) {
        int[][] L = new int[x+1][y+1];
        int z = 0;

        for (int i = 0; i <= x; i++) {
            for (int j = 0; j <= y; j++) {
                if (a.charAt(i) == b.charAt(j)) {
                    if ((i == 0) || (j == 0)) {
                        L[i][j] = 1;
                    } else {
                        L[i][j] = L[i-1][j-1] + 1;
                    }

                    if (L[i][j] > z) {
                        z = L[i][j];
                    }
                } else {
                    L[i][j] = 0;
                }
            }
        }
    }

Но результаты для некоторых входных данных не совпадают, например: 

xalmandriatico
talcolaritriom
13
13

Expected output (using the recursive alg): 8
Actual output (using the iterative alg from wikipedia): 2

Есть идеи о том, что мне нужно делать?

...