3
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – TorbenPutkonen Oct 7 at 12:01
  • \$\begingroup\$ 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? \$\endgroup\$ – a-ina Oct 7 at 12:35
  • \$\begingroup\$ 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. \$\endgroup\$ – TorbenPutkonen Oct 8 at 8:10
  • \$\begingroup\$ @TorbenPutkonen yes, you're right. I should change that in my code \$\endgroup\$ – a-ina Oct 8 at 8:51
0
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thank you. Your suggestions make total sense. I'll change my code to incorporate these changes \$\endgroup\$ – a-ina Oct 9 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.