我现在面临一个问题，我需要计算某个MxM矩阵在NxN中出现的时间（这个矩阵应该大于第一个）。关于如何做到这一点的任何提示？我将在C中实现它，没有选择来改变它。
修订版1
大家好，我真的要感谢所有关于此事的答案和意见。我应该告诉你，经过几个小时的艰苦努力，我们得到的解决方案并不像Boyer-Moore那样严格，而是我自己的算法。我计划在测试和完成后发布它。现在，这些解决方案已经过调整，以便使用具有C Library MPI的大学集群进行速度优化。
我现在面临一个问题，我需要计算某个MxM矩阵在NxN中出现的时间（这个矩阵应该大于第一个）。关于如何做到这一点的任何提示？我将在C中实现它，没有选择来改变它。
修订版1
大家好，我真的要感谢所有关于此事的答案和意见。我应该告诉你，经过几个小时的艰苦努力，我们得到的解决方案并不像Boyer-Moore那样严格，而是我自己的算法。我计划在测试和完成后发布它。现在，这些解决方案已经过调整，以便使用具有C Library MPI的大学集群进行速度优化。
立即浮现在脑海中的一种方法：
将大矩阵视为N * N“字符”的线性字符串，将小矩阵视为长度为（M + 1）* M的线性正则表达式，在每个“行”的前M个位置使用“文字字符”和相当于 .{N-M} 在每行的剩余位置。将正则表达式编译为DFA并运行它。
找到所有匹配的时间是O（N * N）。我怀疑有更好的算法可以工作（更高级的1-d子串搜索算法的改编），但这个并不算太糟糕。
最近，已经开发了用于构建2D后缀树的快速算法。这些可以用于在更大的矩阵中找到任何方形子矩阵，与大矩阵的大小无关：
您可能需要成为订阅者才能看到这些文章。
我也发现了这个免费提供的，它描述了一个随机构造算法 预期 线性时间：
我希望如果你需要在单个矩阵中搜索许多不同的子矩阵，构建一个2D后缀树并用它进行搜索会更快，但是如果你每次都在不同的矩阵内搜索它，它可能比2D Boyer-Moore慢。 。