Algorithm to match a sequence in a given n*m matrix

Question

I have a matrix which is of n*m dimension and i intend to match a set of numbers with the given matrix. It is pretty straight forward if the pattern falls in the vertical or horizontal column of the matrix , but if the pattern falls in a diagonal fashion , i am unable to detect it. For example , if i had to match a given pattern of [-1 , -1 , -1 ] in the following matrix

0 0 0 -1 0

0 0 -1 0 0

0 -1 0 0 0

1 0 -1 -1 -1

In the above case i shud be able to detect the -1 group in the diagonal fashion as well as the one in the last row.

I can also have a input where in

-1 0 0 -1 0

0 -1 0 0 0

0 -1 -1 0 0

1 0 -1 -1 -1

In this case the diagonal from right to left is to be detected and the last row sequence too. Basically on a given sequence i must be able to detect its presence , which could be present in either a vertical way or horizontal or diagonal way.

My Problem: The algorithm has to detect the "all" sequences irrespective of whether its horizontal, vertical or diagonally present. Also , do remember the matrix dimensions are N*M so it could be of any size.

Answer 1

I'll note that you could (somewhat exhaustively) iterate over the n row by m column matrix (treated as a single vector) with different strides -- 1, m-1, m, m+1. At each stride start at every position (up to the point where that stride would run off the end of the vector) and see if you have a match.

This at least eliminates having four different algorithms for the horizontal, vertical, and the two diagonals.

Pretty ugly in terms of algorithm order, though -- pretty much N-squared.

(Well, maybe not. You can qualify the starting cell with a single loop, for all four possibilities. So, once a start has been found, check the four strides. So you should be able to check for everything with one basic pass through the matrix.)