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

How to build Suffix Array O(n)?
Автор SliferSkyd, 3 года назад, По-английски

Hello everyone,

Is there an algorithm to build Suffix Array in complexity O(n)?

Thanks in advance!

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

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

I don't know how to build it in O(n) but, Yes there are algorithms to build Suffix Arrays in O(n).

Li, Li & Huo (2016) gave the first in-place O(n) time suffix array construction algorithm that is optimal both in time and space, where in-place means that the algorithm only needs O(1) additional space beyond the input string and the output suffix array.

Li, Zhize; Li, Jian; Huo, Hongwei (2016). Optimal In-Place Suffix Sorting. Proceedings of the 25th International Symposium on String Processing and Information Retrieval (SPIRE). Lecture Notes in Computer Science. 11147. Springer. pp. 268–284. arXiv:1610.08305. doi:10.1007/978-3-030-00479-8_22. ISBN 978-3-030-00478-1.

source: https://en.wikipedia.org/wiki/Suffix_array

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

You can try to search dc3 algorithm (becareful that there are many wrong implementations)

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

You can build suffix trie in linear time by building SAM on the reversed string so I presume something similar should work for suffix array.

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    Note that SAM works in $$$O(26N)$$$ time, or more generally $$$O(\Sigma N)$$$ time where $$$\Sigma$$$ is the size of the alphabet. There are algorithms which run in $$$O(N)$$$ time even when $$$\Sigma = \Theta(N)$$$, such as DC3 and SAIS.

    → Ответить