String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time

David E. Daykin, Jacqueline W. Daykin, W. F. Smyth

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)

13 Citations (Scopus)

Abstract

In this paper we extend previous work on Unique Maximal Factorization Families (UMFFs) and a total (but non-lexicographic) ordering of strings called V-order. We describe linear-time algorithms for string comparison and Lyndon factorization based on V-order. We propose extensions of these algorithms to other forms of order
Original languageEnglish
Title of host publicationCombinatorial Pattern Matching
Subtitle of host publication22nd Annual Symposium, CPM 2011, Palermo, Italy, June 27-29, 2011. Proceedings
EditorsRaffaele Giancarlo, Giovanni Manzini
PublisherSpringer Nature
Pages65-76
ISBN (Electronic)978-3-642-21458-5
ISBN (Print)978-3-642-21457-8
DOIs
Publication statusPublished - 2011
Externally publishedYes

Publication series

NameCombinatorial Pattern Matching
Volume6661
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fingerprint

Dive into the research topics of 'String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time'. Together they form a unique fingerprint.

Cite this