CODEWITHSUNDEEP
javaalgorithm
Brajesh Kumar
Brajesh Kumar

Reputation: 937

Quickly find matrix in another matrix

if there is a matrix A[][] of order m and another matrix B[][] of order n such that (m>n) you have to find the occurrence of matrix B[][] in matrix A[][].

A[5][5]=
 1,2,3,4,5
 5,4,1,9,7 
 2,1,7,3,4
 6,4,8,2,7
 0,2,4,5,8

B[3][3]=
 1,9,7
 7,3,4
 8,2,7

This matrix B exist in A. I can do it by sliding window algo TC O(p^2*n^2) where p = m-n+1. but I want to do this with minimum time complexity.

Upvotes: 2

Views: 498

Answers (2)

MissingNumber
MissingNumber

Reputation: 1182

There is an abstract which I have found on stack-overflow previously . Hope this should give youwhat are the possible algorithms and approaches you could use . An algorithm for searching for a two dimensional m x m pattern in a two dimensional n x n text is presented.

Upvotes: 0

Aaron Digulla
Aaron Digulla

Reputation: 328724

You can use the Boyer-Moore string search for problems like this:

Compare right to left. In the first row, you compare 3 with 7. 3 doesn't appear in the first row of B, so you can move your window to the right by 3 elements. When you start the loop again, the window doesn't fit into the remains of A's first row. This means you could process the first row with 2 compares.

In the next row, you compare 1 with 7. 1 appears in B, so you move your window just enough that the 1 in B is over the 1 in A.

The next level would then be to start comparing with the lower right corner of B. That would compare 7 with 7. Since 7 appears three times in B, you have to figure out how to move the window efficiently using similar rules as Boyer-Moore.

Upvotes: 2

Related Questions