CODEWITHSUNDEEP
c++algorithmmatrix
NightDev
NightDev

Reputation: 35

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 ?

Upvotes: 2

Views: 458

Answers (2)

notbad
notbad

Reputation: 2877

There is an algorithm better than O(w2h2). Let consider an easier version first. Given a matrix M with only lowercase letters, find the maximum sub-string in the matrix. This problem equals to find the longest common substring in M[0]$1M[1]...M[w-1], where we add distinct special characters between M[i] and M[i+1]. Using a suffix array, the longest common substring problem can be solved in linear time, for this case, it can be solved in O(wh).

For the largest submatrices problem, it can be reduces to the substring problem by enumerating all possible heights l<=h, at the same time, the lexicographical order two substring with height l can inherit from the order of substring with height l-1.

As @Niklas B explained. In the first iteration we rank the row suffixes of the matrix using the suffix array. Then in the second step, we rank the suffixes of adjacent 2-row combinations, using radix sort and by reusing the ranks computed in the first iteration. In the third step, we sort the suffixes of adjacent 3-rows etc. We can also maintain LCP arrays for each iteration so that we can find the longest substring that appears twice, using a single pass.

In total, this algorithm is O(h2w) with a linear time suffix array construction algorithm.

Upvotes: 2

Niklas B.
Niklas B.

Reputation: 95278

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.

Upvotes: 0

Related Questions