Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102329
Title: Computing runs on a general alphabet
Authors: Kosolobov, D.
Issue Date: 2016
Publisher: Elsevier
Citation: Kosolobov D. Computing runs on a general alphabet / D. Kosolobov. — DOI 10.1016/j.ipl.2015.11.016 // Information Processing Letters. — 2016. — Vol. 116. — Iss. 3. — P. 241-244.
Abstract: We describe a RAM algorithm computing all runs (maximal repetitions) of a given string of length n over a general ordered alphabet in O(nlog23 n) time and linear space. Our algorithm outperforms all known solutions working in Θ(nlog σ) time provided σ=nΩ(1), where σ is the alphabet size. We conjecture that there exists a linear time RAM algorithm finding all runs. © 2015 Elsevier B.V.
Keywords: ALGORITHMS
GENERAL ALPHABET
REPETITIONS
RUNS
ALGORITHM COMPUTING
ALPHABET SIZE
GENERAL ALPHABET
LINEAR SPACES
MAXIMAL REPETITIONS
ORDERED ALPHABETS
REPETITIONS
RUNS
ALGORITHMS
URI: http://hdl.handle.net/10995/102329
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 84950122458
PURE ID: 605639
2e27fb4f-8290-4076-87a8-6217d115993c
ISSN: 200190
DOI: 10.1016/j.ipl.2015.11.016
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84950122458.pdf311,88 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.