Fastest way to Find a m x n submatrix in M X N matrix
algorithm, c, c++, matrix
Solution
I recommend doing an internet search on "2d pattern matching algorithms". You'll get plenty of results. I'll just link the first hit on Google, a paper that presents an algorithm for your problem.
You can also take a look at the citations at the end of the paper to get an idea of other existing algorithms.
The abstract:
An algorithm for searching for a two dimensional m x m pattern in a two dimensional n x n text is presented. It performs on the average less comparisons than the size of the text: n^2/m using m^2 extra space. Basically, it uses multiple string matching on only n/m rows of the text. It runs in at most 2n^2 time and is close to the optimal n^2 time for many patterns. It steadily extends to an alphabet-independent algorithm with a similar worst case. Experimental results are included for a practical version.
Problem
I was thinking of a fast method to look for a submatrix m in a bigger mtrix M. I also need to identify partial matches. Couple of approaches I could think of are : - Optimize the normal bruteforce to process only incremental rows and columns. - May be extend Rabin-karp algorithm to 2-d but not sure how to handle partial matches with it. I believe this is quite frequently encountered problem in image processing and would appreciate if someone could pour in their inputs or point me to resources/papers on this topic. EDIT: Smaller example: Bigger matrix: 1 2 3 4 5 4 5 6 7 8 9 7 6 5 2 Smaller Matrix: 7 8 5 2 Result: (row: 1 col: 3) An example of Smaller matrix which qualifies as a partial match at (1, 3): 7 9 5 2 If More than half of pixels match, then it is taken as partial match. Thanks.