Many related questions seem to point to a memory allocation or a memory leak issue, but trying some of the solutions suggested, such as running code with the -Xmx2048m
flag for instance, does not resolve the issue.
This leads me to wonder if there is an issue at the code level, with some kind of infinite loop.
The first file I have is PatternMatching.java
:
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
public static List<Integer> boyerMoore(CharSequence pattern, CharSequence text, CharacterComparator comparator) {
Map<Character, Integer> lastOccurences = buildLastTable(pattern);
List<Integer> listOfOccurrences = new ArrayList<Integer>();
int i = 0;
int m = pattern.length();
int n = text.length();
while (i < n - m + 1) {
int j = m - 1;
while ((j > -1) && (comparator.compare(text.charAt(i+j), pattern.charAt(j)) == 0)) {
j--;
}
if (j == -1) {
listOfOccurrences.add(i);
} else {
int shift = (lastOccurences.get(text.charAt(i+j)) != null) ? lastOccurences.get(text.charAt(i+j)) : -1;
if (shift < j) {
i = i + j - shift;
} else {
i++;
}
}
}
return listOfOccurrences;
}
public static Map<Character, Integer> buildLastTable(CharSequence pattern) {
// WRITE YOUR CODE HERE (DO NOT MODIFY METHOD HEADER)!
int m = pattern.length();
Map<Character, Integer> lastOccurences = new HashMap<Character, Integer>();
for (int i = 0; i < m; i++) {
lastOccurences.put(pattern.charAt(i), i);
}
return lastOccurences;
}
}
And then I try to run it with the following Driver.java
driver file:
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Comparator;
public class Driver {
public static void main(String[] args) {
CharSequence pattern1 = "abacab";
CharSequence text1 = "abacbabadcabacab";
System.out.println(PatternMatching.boyerMoore(pattern1, text1, new CharacterComparator()));
}
}
Here is the error I get when I run the driver with the java -Xmx2048m Driver
command:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.base/java.util.Arrays.copyOf(Arrays.java:3512)
at java.base/java.util.Arrays.copyOf(Arrays.java:3481)
at java.base/java.util.ArrayList.grow(ArrayList.java:237)
at java.base/java.util.ArrayList.grow(ArrayList.java:244)
at java.base/java.util.ArrayList.add(ArrayList.java:454)
at java.base/java.util.ArrayList.add(ArrayList.java:467)
at PatternMatching.boyerMoore(PatternMatching.java:40)
at Driver.main(Driver.java:12)
Any guidance on how to figure out what is happening would be greatly appreciated.