algorithm - 二维模式匹配的最差时间复杂度

Question

使用强力算法进行二维模式匹配的最坏时间复杂度是多少？

如果 haystack-size = n 和 needle-size = m(两者都是正方形)，我觉得它是 O(m^2 * n^2)。

我到达那里的方法是使用一个简单的案例场景，当 m = 2 和 n = 4 时。如果我们在行中水平移动(匹配大海捞针中的 m x m 个字符)，我们将进行 m^2 字符串比较(n - 1)次。我们垂直重复 (n-1) 次。所以，时间 = m^2 (n - 1) x (n - 1) = m^2 * n^2 - 2 * m^2 * n + m*2 = O(m^2 * n^2)。

这个分析正确吗？是 O(m^2 * n^2) 还是应该是 O(m^2 * n^2 - 2 * m^2 * n + m*2)？

编辑:我只是比较两个字符串矩阵或类似两位矩阵的东西。示例:

haystack = [["a", "b", "c", "d"],
            ["e", "f", "g", "h"],
            ["i", "j", "k", "l"],
            ["m", "n", "o", "p"]]
needle = [["j", "k"],
          ["n", "o"]]

Answer 1

匹配2个二维数组，找到所有子数组，我觉得是m*n*o*p(如果第一个数组是m*n，第二个是o*p)，判断是否有单个char火柴。然后我会说你需要将它乘以较大数组的维度，因为这会给你可能的子数组的数量。但毫无疑问，有一种比蛮力法更聪明的方法，即从最小的匹配子数组开始，智能地扩展它，可能使用动态规划。我会研究子串匹配算法，因为这是类似的，但在二维中。