Блог пользователя lawliet_

Автор lawliet_, 11 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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/

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

it's almost like the usual polynomial hash. code

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.