| Full text | |
| Author(s): |
Total Authors: 4
|
| Affiliation: | [1] Univ Sao Paulo, Dept Comp & Math, Sao Paulo - Brazil
[2] McMaster Univ, Dept Comp & Software, Hamilton, ON - Canada
[3] Murdoch Univ, Sch Engn & Informat Technol, Murdoch, WA - Australia
[4] Univ Piemonte Orientale, Comp Sci Inst, Vercelli - Italy
[5] CNR, Inst Informat & Telemat, Pisa - Italy
[6] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil
Total Affiliations: 6
|
| Document type: | Journal article |
| Source: | JOURNAL OF DISCRETE ALGORITHMS; v. 50, p. 2-9, MAY 2018. |
| Web of Science Citations: | 0 |
| Abstract | |
In this paper we present an algorithm to compute the Lyndon array of a string T of length n as a byproduct of the inversion of the Burrows-Wheeler transform of T. Our algorithm runs in linear time using only a stack in addition to the data structures used for Burrows-Wheeler inversion. We compare our algorithm with two other linear-time algorithms for Lyndon array construction and show that computing the Burrows-Wheeler transform and then constructing the Lyndon array is competitive compared to the known approaches. We also propose a new balanced parenthesis representation for the Lyndon array that uses 2n + o(n) bits of space and supports constant time access. This representation can be built in linear time using O(n) words of space, or in O(n log n/log log n) time using asymptotically the same space as T. (C) 2018 Elsevier B.V. All rights reserved. (AU) | |
| FAPESP's process: | 17/09105-0 - Suffix sorting and string similarity measures |
| Grantee: | Felipe Alves da Louza |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |