Omega1's blog

Suffix array 2D
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?

→ Reply
  • »
    »
    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.

    → Reply
    • »
      »
      »
      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

      → Reply