javascript - 二维模式搜索算法

Question

我需要了解二维模式搜索算法。非常感谢提示和链接。

更重要的是:

给定一个矩阵 M[m,n]，其值在 K
例子

000000000000
000001000000
010100010010 = M, K = {0, 1}
010100010001
101111010111

和一个矩阵 L[i, j]，其值在 K + {X} 中代表一个“形状”
例如，字母“L”的形状

1X
1X = L
11

哪些算法可以回答以下问题:

1. 可以在 M 中找到 L 吗？
2. L 可以在 M 中找到多少次(析取 L，没有共同部分(1 或 0))
3. L 可以在 M 中找到多少次(可以有共同的部分(1 或 0))
4. 在 M 中可以找到多少次 L 和 K(K 的定义与 L 类似，K != L)(不相交)等

实现语言是 JavaScript，但任何其他语言都可以。

编辑还发现 this PDF .

Answer 1

看看这个presentation它应该为您提供基本知识。

X 符号可以像通配符一样处理，因此它总是会匹配。

不知道你说的是什么

How many times L, and K (K is defined like L) can be found in M (disjoint) etc.

K 代表字母或形状(如 L)？

确定不相交匹配的最大数量的问题将更加困难。该方法如下:

• 找到所有可能的匹配项
• 创建图，其中节点表示匹配项，边表示两个匹配项具有共同字段。
• 现在您必须在此图中找到最大独立集 (wiki) - 图中的顶点集，其中没有两个相邻，因此不违反问题约束。

编辑:如果您的形状是 L，则可以有效地计算匹配。为列和行创建表格，并为每个单元格检查向上和向右是否匹配。