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

Suffix array 2D
Автор Omega1, история, 9 лет назад, По-английски

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

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

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

Can you please explain more concrate what do you want?

→ Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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

      → Ответить