4 ms·
Suffix arrays, on the other hand, have worse complexity in the typical implementation (O(n) construction, O(k + log(n)) search [1]). However, they work extremel
by danieldk 10y ago
Suffix arrays, on the other hand, have worse complexity in the typical implementation (O(n) construction, O(k + log(n)) search [1]). However, they work extremely well in practice, because they use (contiguous) arrays.
[1] Though there is an O(k) search approach too: http://www.sciencedirect.com/science/article/pii/S1570866703000650 http://www.sciencedirect.com/science/article/pii/S1570866703...
- rocqua 10y agoIf I recall correctly, the linear search approach is based on constant time range minimal query on the suffix array. That feels rather likely to also be worse in real life applications. Heck, as far as I can tell, this approach is just another way of storing a tree.