@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",
}