0

在这之后我完全脑筋急转弯，我需要找到两个文件之间最长的公共子字符串，一个小文件和一个大文件。我什至不知道从哪里开始搜索，这是我到目前为止所拥有的

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

public class MyString
{
    public static void main (String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new FileReader("MobyDick.txt"));
        BufferedReader br2 = new BufferedReader(new FileReader("WarAndPeace.txt"));
        String md, wp;
        StringBuilder s = new StringBuilder();
        while ((md = br.readLine()) != null)
        {
            s.append(md).append(" ");
        }
        md = s + "";
        s.setLength(0);
        while ((wp = br2.readLine()) != null)
        {
            s.append(wp).append(" ");
        }
        wp = s + "";
        s.setLength(0);

        md = md.replaceAll("\\s+", " "); //rids of double spaces
        wp = wp.replaceAll("\\s+", " "); //rids of double spaces
    }
}

到目前为止，我所做的是将每个文件放入一个字符串生成器中，然后放入一个字符串中以消除双空格（它在 MobyDick.txt 上出现了很多）。我找到了这段代码

public static String longestSubstring(String str1, String str2) {

StringBuilder sb = new StringBuilder();
if (str1 == null || str1.isEmpty() || str2 == null || str2.isEmpty())
  return "";

// ignore case
str1 = str1.toLowerCase();
str2 = str2.toLowerCase();

// java initializes them already with 0
int[][] num = new int[str1.length()][str2.length()];
int maxlen = 0;
int lastSubsBegin = 0;

for (int i = 0; i < str1.length(); i++) {
for (int j = 0; j < str2.length(); j++) {
if (str1.charAt(i) == str2.charAt(j)) {
if ((i == 0) || (j == 0))
   num[i][j] = 1;
else
   num[i][j] = 1 + num[i - 1][j - 1];

if (num[i][j] > maxlen) {
  maxlen = num[i][j];
  // generate substring from str1 => i
  int thisSubsBegin = i - num[i][j] + 1;
  if (lastSubsBegin == thisSubsBegin) {
     //if the current LCS is the same as the last time this block ran
     sb.append(str1.charAt(i));
  } else {
     //this block resets the string builder if a different LCS is found
     lastSubsBegin = thisSubsBegin;
     sb = new StringBuilder();
     sb.append(str1.substring(lastSubsBegin, i + 1));
  }
  }
  }
  }}

  return sb.toString();
  }

此代码有帮助，但仅适用于小文件，每次我使用大文件运行它时，都会出现“内存不足：java 堆空间”错误。我需要正确的算法来摆脱堆空间问题，而且我不能增加 java 内存，任何人都可以帮助或指出正确的方向吗？

4

1 回答 1

2

首先，您需要确切地确定为什么这是一个如此大的内存消耗，然后您可以开始解决它。

这个声明作为一个潜在的问题跳出来：

int[][] num = new int[str1.length()][str2.length()];

《战争与和平》的长度超过 300 万个字符，而《白鲸记》的长度大约是它的一半，所以我们保守地说它有 100 万个字符长。

您正在尝试为 3,000,000,000,000 个整数分配空间，每个整数为 4 个字节，计算结果为 12,000,000,000,000 个字节或略低于 11 TB。

希望很清楚为什么该算法不适合这种长度的字符串。

值得庆幸的是，计算机科学的主要理论之一是你总是可以用时间来换取内存，反之亦然。

相反，您想尝试通用后缀树。这具有 \Theta(n + m) 的内存成本，并且可以在更易于管理的 \Theta(n + m) 中构建。

这是生成此类树的 O(n) 算法的极好指南。

一旦你有了后缀树，就可以在恒定时间内找到 LCS，方法是找到树中最深的节点，其子树包含两个输入字符串的子字符串。一个典型的策略是，如果它们满足以下属性，则用标志“i”标记所有节点“v”：

根为 v 的子树包含字符串 S_i 的子字符串

然后找到最深的节点 v，其中对于范围内的所有i（在本例中，只有 0 和 1） ， v 被标记为i 。

于 2014-05-19T20:32:33.603 回答