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

Построение суффиксного массива по суффиксному автомату
Автор Logvinov_Leon, 12 лет назад, По-русски

Доброго времени суток. Кто знает можно ли построить суффиксный массив имея суффиксный автомат за приемлемое время(<O(n^2)). А то автомат я как то понял а массив слабее.

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

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Откуда задача?
>>А то автомат я как то понял, а массив слабее. 
Построение через автомат не сильно поможет понять.

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится
По-моему, вы гвозди микроскопом забиваете. Суфмассив и пишется быстро, и с ним понятно, как правило, что делать (вместо того, чтобы строить аццкие динамики по автомату), и работает быстро. Если непонятно, как строить его за nlogn, то скажу, что он строится нахаляву за nlogn^2 с помощью сортировки непосредственно циклических сдвигов. Но сравнение стоит делать не за линию, конечно, а за логарифм хешами. Вообще полезно научиться писать все суффиксные структуры. А превращение автомат -> массив это скорее интересная алгоритмическая задачка, чем то, что может реально пригодиться.
→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    полезние суффиксные структуры, это бор, суфф. дерево, суфф. массив.. что еще ?
    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится
      Суф. автомат - прикольная штука.
      А больше вроде бы и ничего хорошего нет.
      → Ответить
»
12 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
Я научился только суфф. автомат --> суфф. дерево --> суфф. массив все за O(n)
Но это не проще, чем просто суффиксный массив построить за O(nlogn) 
→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
Вся сложность алгоритма построения суф массива в цифровой сортировке на каждом шаге. Это тот момент, когда мы хотим отсортировать пары, соответствующие удлиненным суффиксам. 
Если он сложно понимается, всегда можно взять и просто кинуть все пары в вектор и запустить sort. Получится, конечно, n log^2 n. Но на стандартных для таких задач 100000 символах он успевает без малейших проблем. А главное не надо думать. Кода получается меньше 10 строк.
→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
"  А то автомат я как то понял а массив слабее. "

Ничего себе зверь. По мне так, суффиксный массив это НАМНОГО проще (и кстати менее применимо) чем суффиксный автомат.
→ Ответить