Prague Stringology Conference 2016

Ondřej Guth

Computing All Approximate Enhanced Covers with the Hamming Distance

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 (n2)-time and a (n)-space algorithm that computes all k-approximate enhanced covers of a string of length n is presented.

Download paper: Article in PostScript Article in PDF BibTeX Reference
 PostScript   PDF   BibTeX reference 
Download presentation: Presentation