Omega1's blog

By Omega1, history, 9 years ago, In English

Hello,I'm very interested how to build a suffix array for a 2D matrix?.Can someone help me.Thanks...

  • Vote: I like it
  • -17
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Can you please explain more concrate what do you want?

  • »
    »
    9 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    We have a matrix: 1 ≤the size of matrix ≤ 400

    0010
    0010
    1101
    1100
    

    and integer k ;

    for this matrix we need to determine the maximum length of the side of a square area whose model appears in the matrix at least k times without rotations. I am think about suffix array in 2D it is possible??

    in the example above the repeating most often submatrix is

    10
    10
    

    which is repeat 2 time.

    I don't have the link of the problem,I only have the problem on paper.

    • »
      »
      »
      9 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I know how to solve it for O(n2 * log3n) using hashs

      1) Binary search for answer

      2) Trying all possible matrixes with some side and saving their hashes

      3) find most common element in hashes array and compare it with k