Java中的Knuth-Morris-Pratt算法在矩阵中查找子串

Question

给定两个矩阵的问题:模式p和文本t。编写一个计算p在t中出现的次数的程序。输入第一行包含两个数字x和y --模式中的行数和列数。下一个x行中的每一行都包含一个长度为y的字符串。下面的行包含相同格式的文本。保证模式和文本的行和列的大小都不等于零。输出文本中模式出现的次数。

这是我的解决办法。我想了解一下这方面的代码：

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;
    }
}

示例输入1:

1 1

一个

2 2

ab

基数

示例输出1:

2

Answer 1

对象

如果有一个地方可以喝，那就是Java。您的static main应该受到更多的限制。考虑：

• 使findOccurrences成为实例，而不是static方法
• 给Matrix一个接受Scanner的构造函数，以及另一个接受ints的构造函数
• 使patternMatrix和textMatrix实例成员变量
• 从findOccurrences中删除所有方法参数，并让它使用成员

这种模式有助于测试性和重新进入。可能更正确的(tm)操作是将Matrix类与入口点类完全分开。

丢弃输入

第一行包含两个数字x和y-模式中的行数和列数。

你忽视了y。这是故意的吗？您肯定希望解析它并保存它，甚至可能验证字符串长度。