Knuth-Morris-Pratt algorithm in Java Finding substrings in a matrix

Question

Problem

Given two matrices: a pattern p and a text t. Write a program that counts the number of occurrences of p in t.

Input

the first line contains two numbers x and y -- the number of rows and columns in a pattern. Each of the next x lines contains a string of length y. The following lines contain a text in the same format. It is guaranteed that the sizes of rows and columns both for the pattern and for the text are not equal to zero.

Output

the number of occurrences of the pattern in the text.

Here is my solution. I would like to get a code review on this:

import java.util.*;
public class Matrix {
 public static void main(String[] args) {
 Scanner scanner = new Scanner(System.in);
 String[] patternMatrix = new String[Integer.parseInt(scanner.nextLine().split(" ")[0])];
 for (int i = 0; i < patternMatrix.length; i++) {
 patternMatrix[i] = scanner.nextLine();
 }
 String[] textMatrix = new String[Integer.parseInt(scanner.nextLine().split(" ")[0])];
 for (int i = 0; i < textMatrix.length; i++) {
 textMatrix[i] = scanner.nextLine();
 }
 long t = System.currentTimeMillis();
 System.out.println(findOccurrences(textMatrix, patternMatrix));
 System.out.println("Time: " + (System.currentTimeMillis() - t));
 }
 private static int findOccurrences(String[] textMatrix, String[] patternMatrix) {
 int occurrences = 0;
 for (int i = 0; i < textMatrix.length; i++) {
 // check if you have appropriate remaining rows
 if (textMatrix.length - 1 - i < patternMatrix.length - 1) {
 break;
 }
 // check if you can find the first row
 List<Integer> indices = occurrences(textMatrix[i], patternMatrix[0]);
 if (indices.isEmpty()) {
 continue;
 }
 for (int j = i + 1, a = 1; a <= patternMatrix.length - 1; j++, a++) {
 if (textMatrix[j].equals(textMatrix[j - 1]) && patternMatrix[a].equals(patternMatrix[a - 1])) {
 continue;
 }
 Iterator<Integer> iterator = indices.iterator();
 while (iterator.hasNext()) {
 int index = iterator.next();
 if (!textMatrix[j].substring(index, index + patternMatrix[a].length()).equals(patternMatrix[a])) {
 iterator.remove();
 }
 }
 if (indices.isEmpty()) {
 break;
 }
 }
 occurrences += indices.size();
 }
 return occurrences;
 }
 private static int[] prefixFunction(String str) {
 /* 1 */
 int[] prefixFunc = new int[str.length()];
 /* 2 */
 for (int i = 1; i < str.length(); i++) {
 /* 3 */
 int j = prefixFunc[i - 1];
 while (j > 0 && str.charAt(i) != str.charAt(j)) {
 j = prefixFunc[j - 1];
 }
 /* 4 */
 if (str.charAt(i) == str.charAt(j)) {
 j += 1;
 }
 /* 5 */
 prefixFunc[i] = j;
 }
 /* 6 */
 return prefixFunc;
 }
 private static List<Integer> occurrences(String text, String pattern) {
 int[] prefixArray = prefixFunction(pattern);
 List<Integer> occurrencesList = new ArrayList<>();
 int j = 0;
 for (int i = 0; i < text.length(); i++) {
 while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
 j = prefixArray[j - 1];
 }
 if (text.charAt(i) == pattern.charAt(j)) {
 j++;
 }
 if (j == pattern.length()) {
 occurrencesList.add(i - pattern.length() + 1);
 j = prefixArray[j - 1];
 }
 }
 return occurrencesList;
 }
}

Sample Input 1:

1 1

a

2 2

ab

ba

Sample Output 1:

2

• TorbenPutkonen: For starters, there's no need to check the bottom 99 rows or last 99 columns if the pattern is 100x100. Next you should document the algorithm with JavaDoc. I'm way too lazy to try to figure out what the "prefixFunction" tries to achieve.
• a-ina: It's okay if you don't understand the Prefix Function because that's been given to me, it's part of the KMP algorithm. I have to optimise findOccurrences function. Also, why don't I need to check the last 99 columns or rows if the pattern is 100x100?
• TorbenPutkonen: I mean that if the pattern does not start at the 100th to last row/column, it won't start after it, because it won't fit.
• a-ina: @TorbenPutkonen yes, you're right. I should change that in my code

Answer 1

Objects

If there's a place to drink OOP kool-aid, it's Java. Your static main should be much more limited. Consider:

• Make findOccurrences an instance, not static, method
• Give Matrix a convenience constructor accepting a Scanner, and another constructor accepting two ints
• Make patternMatrix and textMatrix instance member variables
• Remove all method parameters from findOccurrences and have it use members instead

This pattern helps with testability and re-entrance. The Probably More Correct (tm) thing to do is separate the Matrix class entirely from your entry point class.

Discarding input

the first line contains two numbers x and y -- the number of rows and columns in a pattern.

You're ignoring y. Is that deliberate? You'll definitely want to parse it and hold onto it, and maybe even validate the string lengths.

• a-ina: Thank you. Your suggestions make total sense. I'll change my code to incorporate these changes