title: is there any paper or an explanation on how to implement a two dimensional KMP?
body: <p>I tried to solve the problem of two dimensional search using a combination of Aho-Corasick and a single dimensional KMP, however, I still need something faster.</p>
  
  <p>To elaborate, I have a matrix A of characters of size n1*n2 and I wish to find all occurrences of a smaller matrix B of size m1*m2 and I want that to be in O(n1*n2+m1*m2) if possible.</p>
  
  <p>For example: </p>
  
  <pre><code>A = a b c b c b
      b c a c a c
      d a b a b a
      q a s d q a
  </code></pre>
  
  <p>and </p>
  
  <pre><code>B = b c b
      c a c
      a b a
  </code></pre>
  
  <p>the algorithm should return the indexes of say, the upper left corner of the match, which in this case should return (0,1) and (0,3). notice that the occurrences may overlap.</p>