Самая длинная повторяющаяся и не перекрывающаяся подстрока в огромной строке - PullRequest
Новая
       10

Самая длинная повторяющаяся и не перекрывающаяся подстрока в огромной строке

0 голосов
/ 09 января 2020

Я использовал эту программу, чтобы найти самую длинную повторяющуюся подстроку в строке. Я нашел его по этой ссылке (https://www.geeksforgeeks.org/longest-repeating-and-non-overlapping-substring/). Эта программа отлично работает, если мой ввод - строка меньшего размера. 

    static String longestRepeatedSubstring(String str) { 
        int n = str.length(); 
        int LCSRe[][] = new int[n + 1][n + 1]; 

        String res = ""; // To store result  
        int res_length = 0; // To store length of result  

        int i, index = 0; 
        for (i = 1; i <= n; i++) { 
            for (int j = i + 1; j <= n; j++) { 
                if (str.charAt(i - 1) == str.charAt(j - 1) 
                        && LCSRe[i - 1][j - 1] < (j - i)) { 
                    LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1; 

                    if (LCSRe[i][j] > res_length) { 
                        res_length = LCSRe[i][j]; 
                        index = Math.max(i, index); 
                    } 
                } else { 
                    LCSRe[i][j] = 0; 
                } 
            } 
        } 

        if (res_length > 0) { 
            for (i = index - res_length + 1; i <= index; i++) { 
                res += str.charAt(i - 1); 
            } 
        } 

        return res; 
    } 

    public static void main(String[] args) { 
        String str = "abracadabra"; 
        System.out.println(longestRepeatedSubstring(str)); 
    }

Однако у меня есть строка, которая имеет 14553776 символов, и когда я запускаю программу, я всегда получаю java.lang.OutOfMemoryError: Java heap space. Я пытался увеличить размер кучи и эту вещь с виртуальной памятью.

Интересно, есть ли способ решить эту проблему. Мэйби, улучшая программу или любое другое решение?

Спасибо за помощь

1 Ответ

0 голосов
/ 09 января 2020

Это потому, что этот код сохраняет результаты в виде новой строки: 

String res = ""; // To store result

, поэтому здесь: 

for (i = index - res_length + 1; i <= index; i++) { 
            res += str.charAt(i - 1); 
        }

есть утечка памяти. Вместо этого вам нужно хранить индексы строки результата.

...