I faced a problems on vn.spoj.com related to hasing string in the shape of rectangle. This is the link of the problem : http://vn.spoj.com/problems/MESSAGE1/
It says find the maximum area of a rectangle that appears in both input rectangle M * N (the same size)
M, N <= 100;
The rectangle only consists of lower Latin words.
Please help me with this, I've gotten struck with it many days.
P.s Sorry at my bad English :D
I am not sure if I understand very well the problem statement but I think you can build a new matrix with (**LONG_MIN**) and 1 where 1 means the letter matches in both matrices in position (i,j). Then apply Maximum Sum Sub-rectangle algorithm taking the rectangle with maximum positive sum. I hope it can help.
EDITED:
Maybe it could help: http://stackoverflow.com/questions/3814040/finding-the-maximum-sum-sub-rectangle-within-a-matrix http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/
it's almost like the usual polynomial hash. code
You can use normal hashing algorithm for strings (Rabin-Karp matcher) for this problem too. since in this case the area shape is always the same, maybe you need to choose the base according to values of M,N to have less expectation of invalid occurences of hashing value.