巨大字符串中最长的重复且不重叠的子字符串

Question

我使用此程序在字符串中找到最长的重复子字符串。我在此链接（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。我曾尝试增加堆大小，并使用虚拟内存来增加此功能。

我想知道是否有解决此问题的方法。 Maby正在改进程序或任何其他解决方案？

感谢您的帮助

Answer 1

那是因为此代码将结果存储为新字符串：

String res = ""; // To store result

所以在这里：

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

存在内存泄漏。您需要存储结果字符串的索引。