Q:

Largest equal submatrices in bigger matrix

Suppose you have one matrix of height h and width w (h,w <= 500) You have to find two submatrices of same size that are equal. Any idea for solving ?

A:

You can enumerate all vectors (-h < dh < h, 0 <= dw < w) in O(hw). For each such vector, translate the matrix by the vector (dh, dw) and subtract the translated matrix from the original one. In the range where they overlap you want to find the rectangle of zeroes that has the largest area. You can use a linear time algorithm to do that.
Runtime: O(w2h2)
A more pragmatic approach would be to hash all submatrices and check for duplicates that way. This would have the same expected runtime.

