title: Fast counting of 2D sub-matrices withing a large, dense 2D matrix?
body: <p>What's a good algorithm for counting submatrices within a larger, dense matrix? If I had a single line of data, I could use a suffix tree, but I'm not sure if generalizing a suffix tree into higher dimensions is exactly straightforward or the best approach here.</p>
  
  <p>Thoughts?</p>
  
  <p>My naive solution to index the first element of the dense matrix and eliminate full-matrix searching provided only a modest improvement over full-matrix scanning.</p>
  
  <p>What's the best way to solve this problem?</p>
  
  <pre><code>Example:
  
  Input:
  
  Full matrix:
  123
  212
  421
  
  Search matrix:
  12  
  21  
  
  Output:
  2
  </code></pre>
  
  <p>This sub-matrix occurs <strong>twice</strong> in the full matrix, so the output is 2. The full matrix could be 1000x1000, however, with a search matrix as large as 100x100 (variable size), and I need to process a number of search matrices in a row. Ergo, a brute force of this problem is far too inefficient to meet my sub-second search time for several matrices.</p>