Computing All Approximate Enhanced Covers with the Hamming Distance

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F16%3A00300852" target="_blank" >RIV/68407700:21240/16:00300852 - isvavai.cz</a>
Result on the web
<a href="http://www.stringology.org/event/2016/p13.html" target="_blank" >http://www.stringology.org/event/2016/p13.html</a>
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Computing All Approximate Enhanced Covers with the Hamming Distance
Original language description
A border p of a string x is an enhanced cover of x if the number of positions of x that lie within some occurrence of p is the maximum among all borders of x. In this paper, more general notion based on the enhanced cover is introduced: a k-approximate enhanced cover, where fixed maximum number of errors k in the Hamming distance is considered. The k-approximate enhanced cover of x is its border and its k-approximate occurrences are also considered in the covered number of positions of x. An O(n^2)-time and a O(n)-space algorithm that computes all k-approximate enhanced covers of a string of length n is presented.
Czech name
—
Czech description
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Proceedings of the Prague Stringology Conference 2016
ISBN
978-80-01-05996-8
ISSN
—
e-ISSN
—
Number of pages
12
Pages from-to
146-157
Publisher name
Czech Technical University in Prague
Place of publication
Praha
Event location
Praha
Event date
Aug 29, 2016
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000390865400013

Similar results(10)