Optimal suffix sorting and LCP array construction for constant alphabets
详细信息 查看全文
- 作者：Felipe A. Louzaa ; louza@ic.unicamp.br" class="auth_mail" title="E-mail the corresponding author ; Simon Gogb ; gog@kit.edu" class="auth_mail" title="E-mail the corresponding author ; Guilherme P. Tellesa ; gpt@ic.unicamp.br" class="auth_mail" title="E-mail the corresponding author
- 关键词：Data structures ; Suffix array ; LCP array ; Linear time ; Constant space
- 刊名：Information Processing Letters
- 出版年：2017
- 出版时间：February 2017
- 年：2017
- 卷：118
- 期：Complete
- 页码：30-34
- 全文大小：299 K
文摘
- •
A time and space optimal suffix and LCP arrays construction for constant alphabets is proposed.
- •
The algorithm can be viewed as an adaptation of (Fischer, WADS'11) to (Nong, 2013).
- •
The algorithm runs in linear time using constant workspace.
- •
Performance of our algorithm is competitive in practice.
- •
The source code is publicly available at github.