2D Rabin Karp
Posted: Mon Oct 16, 2006 6:37 pm
problem:
suppose that there is a M*N matrix, and there is a m*n matrix where m <= M && N <= n, compute the number of occurance of the small matrix in the big one...
i'm thinking to use rabin karp algorithm to solve this problem, but i kinda confuse on how to efficiently compute the hash value.
In 1D Rabin Karp, h = (((h[i-1] - c[i-1]*(K^L)) * K ) + c[i+L-1]) mod K... where L is the small string length & K is a constant (usually a big prime number). How can we use the same method in 2D?
Thanks in advance
a little bit mistype in previous post...
suppose that there is a M*N matrix, and there is a m*n matrix where m <= M && N <= n, compute the number of occurance of the small matrix in the big one...
i'm thinking to use rabin karp algorithm to solve this problem, but i kinda confuse on how to efficiently compute the hash value.
In 1D Rabin Karp, h = (((h[i-1] - c[i-1]*(K^L)) * K ) + c[i+L-1]) mod K... where L is the small string length & K is a constant (usually a big prime number). How can we use the same method in 2D?
Thanks in advance
a little bit mistype in previous post...