lawliet_'s blog

Need help for hashing string on the table

By lawliet_, 11 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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/

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

it's almost like the usual polynomial hash. code

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply