Lets say I want develop a pattern matching algorithm.

Input file contains dimensions of 'pattern' and the 'pattern' matrix itself.

Next it contains the dimensions of 'match' and the 'match' matrix itself.

The dimension of these matrix theoretically can range to infinity.

However, the goal is come with an algorithm that can do this when pattern_dimensions < match_dimensions

To keep it simple lets say match_dimensions_max = 1000000x1000000 and

the 'match' and 'pattern' matrix both only contains 0s and 1s.

Typical simple inputs loaded from a file to the program to paint the picture:

'pattern' Array size : 2 X 2

Contents of 'pattern' array

|0|1|
|0|0|
-----

'match' Array size: 3 x 5

Contents of 'match' array

|0|1|0|1|0|
|0|0|0|0|0|
|1|0|0|0|1|
-----------

Here I need to only match 0 zeros from 'pattern' array to 'match' array.

|0| |
|0|0|

This is what I should match and 1 has no significance to positive match. If you match it you will see it has four matches

    2x|0|1|       
      |0|0|
    and
    2x|0|0|
      |0|0|

What would be an efficient algorithm to check this? for this 'pattern' and 'match' array my output should be 4

CodePudding user response：

#include "headers/main.h"

int search_arctic_find_match(char **search_image,int search_row,int search_col,
               char **arctic_image,int arctic_row,int arctic_col){
    
    assert(
        search_image != NULL      &&       \
        arctic_image != NULL      &&       \
        search_row < arctic_row   &&       \
        search_col < arctic_col            \
    );

    /* A VARIABLE THAT KEEPS COUNT OF NUMBER OF MATCHES */
    int count = 0;

    /* THESE TWO LOOPS TRAVERSES MATCHABLE BLOCKS OF ARCTIC IMAGE */
    for(int i=0;i search_row-1<arctic_row;i  ) {
        for(int j=0;j search_col-1<arctic_col;j  ) {

            /* SEARCH ROW AND COLUMN INDEX ARE USED TO ITERATE SEARCH IMAGE */
            int search_row_idx = 0;
            int search_col_idx = 0;

            /* FLAG THAT DEFAULTS AT MATCHED AND EQUALS NOT_MATCHED WHEN A DISCREPANCY IS FOUND */
            int flag = MATCHED;

            
            for(int m = i;m < i search_row;m  ) {
                for(int n=j;n< j search_col;n  ) {

                    if(search_image[search_row_idx][search_col_idx]=='0' && arctic_image[m][n]!=search_image[search_row_idx][search_col_idx]) { 
                        /* IF THE CONDITION IS SATISFIED THEN SET THE FLAG = NOT_MATCHED */
                        flag = NOT_MATCHED;
                        /* AT NOT MATCHED BREAK THE LOOP. NO NEED TO CHECK FURTHER */
                        break;
                    }

                    /* INCREMENT SEARCH COLUMN INDEX */ 
                    search_col_idx  ;
                }
                /* RESET SEARCH COLUMN INDEX TO 0 */    
                search_col_idx=0;
                /* INCREMENT SEARCH ROW INDEX */
                search_row_idx  ;
            }
            /* RESET SEARCH ROW INDEX TO 0 */
            search_row_idx=0;
            /* IF FLAG UNCHANGED INCREMENT COUNT  */
            if(flag==MATCHED) {
                count  ;
            }       
        }   
    }
    /* RETURNS NUMBER OF MATCHES  */        
    return count;   
}