SliferSkyd's blog

How to build Suffix Array O(n)?
By SliferSkyd, 4 years ago, In English

Hello everyone,

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

Thanks in advance!

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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.

    → Reply