I'm trying to solve a problem here, it asks to find the size of the biggest common subsquare between two matrices.
e.g.
Matrix #1
3 3
1 2 0
1 2 1
1 2 3
Matrix #2
3 3
0 1 2
1 1 2
3 1 2
Answer: 2
Biggest common subsquare is:
1 2
1 2
I know that Rabin-Karp algorithm can be extended to work on a 2D matrix, but I can't understand how exactly can we do that, I tried to understand the author's code in the editorial, but its too complicated, I also did some search for a good explanation, but I couldn't find a clear one.
Can anyone simply explain how can I use Rabin-Karp algorithm to hash a matrix, I know I will hash rows and columns, but I can't see how to mix their hashes together to come up with a hashed matrix, and how the rolling hash function will be handled in this case ?