title: find a matrix in a big matrix
body: <p>I have a very large <code>n*m</code> matrix <code>S</code>. I want to efficiently determine whether there exists a submatrix <code>F</code> inside of <code>S</code>. The large matrix <code>S</code> can have a size as big as <code>500*500</code>.</p>
  
  <p>To clarify, consider the following:</p>
  
  <pre><code>S = 1 2 3 
      4 5 6
      7 8 9
  
  F1 = 2 3 
       5 6
  
  F2 = 1 2 
       4 6
  </code></pre>
  
  <p>In such a case:</p>
  
  <ul>
  <li><code>F1</code> is inside <code>S</code></li>
  <li><code>F2</code> is not inside <code>S</code></li>
  </ul>
  
  <p>Each element in the matrix is a <code>32-bit</code> integer. I can only think of using a brute-force approach to find whether <code>F</code> is a submatrix of <code>S</code>. I googled to find an effective algorithm, but I can't find anything.</p>
  
  <p>Is there some algorithm or principle to do it faster? (Or possibly some method to optimize the brute force approach?)</p>
  
  <p>PS the statistics data</p>
  
  <pre><code>A total of 8 S
  On average, each S will be matched against about 44 F.
  The probability of success match (i.e. F appears in a S) is 
  19%.
  </code></pre>