find a matrix in a big matrix

Question

I have a very large n*m matrix S. I want to efficiently determine whether there exists a submatrix F inside of S. The large matrix S can have a size as big as 500*500.

To clarify, consider the following:

S = 1 2 3 
    4 5 6
    7 8 9

F1 = 2 3 
     5 6

F2 = 1 2 
     4 6

In such a case:

• F1 is inside S
• F2 is not inside S

Each element in the matrix is a 32-bit integer. I can only think of using a brute-force approach to find whether F is a submatrix of S. I googled to find an effective algorithm, but I can't find anything.

Is there some algorithm or principle to do it faster? (Or possibly some method to optimize the brute force approach?)

PS the statistics data

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%.

Answer 1

It involves preprocessing the matrix. This will be heavy on memory, but it should be better in terms of computation time.

• Check if the size of the sub-matrix is less than that of the matrix before you do the check.
• While constructing the matrix, build a construct that maps a value in the matrix to an array of (x,y) positions in the matrix. This will allow you to check for the existence of a sub-matrix where candidates could exist. You would use the value at (0,0) in the sub-matrix and get the possible positions of this value in the larger matrix. If the list of positions is empty, you have no candidates, and so, the sub-matrix does not exist. There's a start (More experienced people might consider this a naive approach however).

Answer 2

If you want to query multiple times for a same big matrix and same size submatrices. There are many solutions to preprocess the big matrix.

A similar ( or even same ) problem is here.

Fastest way to Find a m x n submatrix in M X N matrix

Answer 3

Since you only want to know whether a given matrix is inside another big matrix. If you know how to use Matlab code from C++, you may directly use ismember from Matlab. Another way may be try to figure out how ismember works in Matlab, then implement the same thing in C++.

See Find location of submatrix

Answer 4

Since you have tagged the question as C++ also, I am providing this code. This is a brute force technique and definitely not the ideal solution for this problem. For an S X T Main Matrix and a M X N Sub Matrix, the time complexity of the algorithm is O(STMN).

cout<<"\nEnter the order of the Main Matrix";
cin>>S>>T;
cout<<"\nEnter the order of the Sub Matrix";
cin>>M>>N;

// Read the Main Matrix into MAT[S][T]

// Read the Sub Matrix into SUB[M][N]

for(i=0; i<(S-M); i++)
{
   for(j=0; j<(T-N); j++)
   {
      flag=0;
      for(p=0; p<M; p++)
      {
         for(q=0; q<N; q++)
         {
            if(MAT[i+p][j+q] != SUB[p][q])
            {
               flag=1;
               break; 
            }
         }
         if(flag==0)
         {
            cout<<"Match Found in the Main Matrix at starting location "<<(i+1) <<"X"<<(j+1);
            break;
         }
      }
      if(flag==0)
      {
         break;
      }
   }            
   if(flag==0)
   {
      break;
   }
}