Prague Stringology Conference 2012
Tomáš Flouri, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Simon J. Puglisi, William F. Smyth and Wojciech Tyczyński
New and Efficient Approaches to the Quasiperiodic Characterisation of a String
| Abstract: |
| A factor u of a string y is a cover of y if every letter of y lies within some occurrence of u in y; thus every cover u is also a border – both prefix and suffix – of y. A string y covered by u thus generalises the idea of a repetition; that is, a string composed of exact concatenations of u. Even though a string is coverable somewhat more frequently than it is a repetition, still a string that can be covered by a single u is rare. As a result, seeking to find a more generally applicable and descriptive notion of cover, many articles were written on the computation of a minimum k-cover of y; that is, the minimum cardinality set of strings of length k that collectively cover y. Unfortunately, this computation turns out to be NP-hard. Therefore, in this article, we propose new, simple, easily-computed, and widely applicable notions of string covering that provide an intuitive and useful characterisation of a string and its prefixes: the enhanced cover and the enhanced cover array. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |