Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102329
Full metadata record
DC FieldValueLanguage
dc.contributor.authorKosolobov, D.en
dc.date.accessioned2021-08-31T15:03:10Z-
dc.date.available2021-08-31T15:03:10Z-
dc.date.issued2016-
dc.identifier.citationKosolobov 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.en
dc.identifier.issn200190-
dc.identifier.otherFinal2
dc.identifier.otherAll Open Access, Green3
dc.identifier.otherhttps://www.scopus.com/inward/record.uri?eid=2-s2.0-84950122458&doi=10.1016%2fj.ipl.2015.11.016&partnerID=40&md5=d9d94bc5506c7bf1364407818c1a6d3c
dc.identifier.otherhttp://arxiv.org/pdf/1507.01231m
dc.identifier.urihttp://hdl.handle.net/10995/102329-
dc.description.abstractWe 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.en
dc.format.mimetypeapplication/pdfen
dc.language.isoenen
dc.publisherElsevieren
dc.rightsinfo:eu-repo/semantics/openAccessen
dc.sourceInf. Process. Lett.2
dc.sourceInformation Processing Lettersen
dc.subjectALGORITHMSen
dc.subjectGENERAL ALPHABETen
dc.subjectREPETITIONSen
dc.subjectRUNSen
dc.subjectALGORITHM COMPUTINGen
dc.subjectALPHABET SIZEen
dc.subjectGENERAL ALPHABETen
dc.subjectLINEAR SPACESen
dc.subjectMAXIMAL REPETITIONSen
dc.subjectORDERED ALPHABETSen
dc.subjectREPETITIONSen
dc.subjectRUNSen
dc.subjectALGORITHMSen
dc.titleComputing runs on a general alphabeten
dc.typeArticleen
dc.typeinfo:eu-repo/semantics/articleen
dc.typeinfo:eu-repo/semantics/publishedVersionen
dc.identifier.doi10.1016/j.ipl.2015.11.016-
dc.identifier.scopus84950122458-
local.contributor.employeeKosolobov, D., Ural Federal University, Ekaterinburg, Russian Federation
local.description.firstpage241-
local.description.lastpage244-
local.issue3-
local.volume116-
local.contributor.departmentUral Federal University, Ekaterinburg, Russian Federation
local.identifier.pure605639-
local.identifier.pure2e27fb4f-8290-4076-87a8-6217d115993cuuid
local.identifier.eid2-s2.0-84950122458-
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.