Abstract | ||
---|---|---|
Recently, Holt and McMillan [Bionformatics 2014, ACM-BCB 2014] have proposed a simple and elegant algorithm to merge the Burrows-Wheeler transforms of a family of strings. In this paper we show that the Hu0026M algorithm can be improved so that, in addition to merging the BWTs, it can also merge the Longest Common Prefix (LCP) arrays. The new algorithm, called Gap because of how it operates, has the same asymptotic cost as the Hu0026M algorithm and requires additional space only for storing the LCP values. |
Year | Venue | Field |
---|---|---|
2016 | arXiv: Data Structures and Algorithms | LCP array,Discrete mathematics,Combinatorics,Merge (version control),Mathematics |
DocType | Volume | Citations |
Journal | abs/1609.04618 | 0 |
PageRank | References | Authors |
0.34 | 9 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Giovanni Manzini | 1 | 1584 | 111.42 |