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

Автор _Nyu_, история, 6 лет назад, По-английски

Is there any Linear Time algorithm to build Suffix Array? Please provide source code or algorithm link.....

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

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

For this you can build a suffix tree in O(n) and then convert it into a suffix array by performing a lexicographic DFS on the suffix tree.

See this for more.

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

Yes. At least one such algorithm is DC3. However I don't know if linear time construction is any faster than for usual input sizes.

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

SA-IS algorithm has linear complexity, and is competitive with the time algorithms. You can find a simple description here and the original paper with some implementation here.