@inproceedings{733d6274827940e48d4eadbe7c2a1eb8,
title = "Applications of V-Order: Suffix Arrays, the Burrows-Wheeler Transform & the FM-index",
abstract = "V-order is a total order on strings that determines an instance of Unique Maximal Factorization Families (UMFFs), a generalization of Lyndon words. The fundamental V-comparison of strings can be done in linear time and constant space. V-order has been proposed as an alternative to lexicographic order (lexorder) in the computation of suffix arrays and in the suffix-sorting induced by the Burrows-Wheeler transform (BWT). In line with the recent interest in the connection between suffix arrays and the Lyndon factorization, we in this paper make a first attempt to obtain similar results for the V-order factorization. Indeed, we show that the results describing the connection between suffix arrays and the Lyndon factorization are matched by analogous V-order processing. We then apply the V-BWT to implement pattern matching in V-order after suitably modifying the FM-index.",
keywords = "Combinatorics, FM-index, Lexorder, Pattern matching, String comparison, Suffix sorting, V-BWT, V-order",
author = "Ali Alatabbi and Daykin, {Jacqueline W.} and Neerja Mhaskar and Rahman, {M. Sohel} and Smyth, {W. F.}",
note = "Funding Information: Acknowledgements. The third and fifth authors were funded by NSERC Grant Number: 10536797. The fourth author was partially supported by a grant from Pub-ali Bank Ltd., Bangladesh. The second author was part-funded by the European Regional Development Fund through the Welsh Government, Grant Number 80761-AU-137 (West): Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG.",
year = "2019",
month = feb,
day = "16",
doi = "10.1007/978-3-030-10564-8_26",
language = "English",
isbn = "978-3-030-10563-1",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "329--338",
editor = "Shin-ichi Nakano and Krishnendu Mukhopadhyaya and Das, {Gautam K.} and Mandal, {Partha S.}",
booktitle = "WALCOM",
address = "Switzerland",
}