How to extend rabin karp to look for an mxm pattern among nxn characters?
Can anyone come up with a pseudo code? And Will there be any affect on the time complexity of the algorithm?
One approach would be in three steps:
1) For each horizontal line, use the Rabin-Karp rolling hash to compute hash values covering each contiguous stretch of hash characters of length k along that line.
2) For each column, use the Rabin-Karp rolling hash down the column to take hash values computed in step(1) for contiguous stretches of text of length k which lie immediately above and below each other and compute a combined hash value which corresponds to a rectangle of text.
3) Look up that rectangle of text as before.
In step 2 we start from values of the form X[0] + X[1]*P + X[1]*P^2+... produced by step 1. If you use the multiplier P^k for the second step, you should be able to end up with a hash function on a rectangle identical to that if you rearranged the rectangle as a single line a computed a single long Rabin-Karp hash.
As described above, you need enough store to hold hash values for all of the rectangular input. It should be easy to reduce this to enough store to hold a rectangle of hash values running along the input but only going about as deep as the pattern you are searching for. Possibly you could do better if you put your mind to it, and did a little more computation. Clearly you could divide the region up before searching at the cost of redoing squares along the border of your division.