Proceedings of the ACM-SIAM Symposium on Discrete Algorithms

Сан-Диего : SIAM, 2015.

Научный редактор: P. Indyk

This symposium focuses on research topics related to efficient algorithms and data structures for discrete problems. In addition to the design of such methods and structures, the scope also includes their use, performance analysis, and the mathematical problems related to their development or limitations. Performance analyses may be analytical or experimental and may address worst-case or expected-case performance. Studies can be theoretical or based on data sets that have arisen in practice and may address methodological issues involved in performance analysis.

Главы книги

Wavelet Trees Meet Suffix Trees

Бабенко М. А., Gawrychowski P., Kociumaka T. и др., , in: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms.: San Diego: SIAM, 2015. P. 572–591.

We present an improved wavelet tree construction algorithm and discuss its applications to a number of rank/select problems for integer keys and strings. Given a string of length n over an alphabet of size ω ≤ n, our method builds the wavelet tree in O(n log ω √log n) time, improving upon the state-of-the-art algorithm ...

Добавлено: 4 октября 2014 г.

Ключевые слова: Discrete Algorithms