Catalog Home Page

Enhanced covers of regular & indeterminate strings using prefix tables

Alatabbi, A., Sohidull Islam, A.S., Rahman, M.S., Simpson, J. and Smyth, W.F. (2015) Enhanced covers of regular & indeterminate strings using prefix tables. Unpublished Publication .

PDF (Pre-print)
Download (704kB)
Link to Open Access version:
*No subscription required


A \itbf{cover} of a string x=x[1..n] is a proper substring u of x such that x can be constructed from possibly overlapping instances of u. A recent paper \cite{FIKPPST13} relaxes this definition --- an \itbf{enhanced cover} u of x is a border of x (that is, a proper prefix that is also a suffix) that covers a {\it maximum} number of positions in x (not necessarily all) --- and proposes efficient algorithms for the computation of enhanced covers. These algorithms depend on the prior computation of the \itbf{border array} β[1..n], where β[i] is the length of the longest border of x[1..i], 1≤i≤n. In this paper, we first show how to compute enhanced covers using instead the \itbf{prefix table}: an array π[1..n] such that π[i] is the length of the longest substring of x beginning at position i that matches a prefix of x. Unlike the border array, the prefix table is robust: its properties hold also for \itbf{indeterminate strings} --- that is, strings defined on {\it subsets} of the alphabet Σ rather than individual elements of Σ. Thus, our algorithms, in addition to being faster in practice and more space-efficient than those of \cite{FIKPPST13}, allow us to easily extend the computation of enhanced covers to indeterminate strings. Both for regular and indeterminate strings, our algorithms execute in expected linear time. Along the way we establish an important theoretical result: that the expected maximum length of any border of any prefix of a regular string x is approximately 1.64 for binary alphabets, less for larger ones

Publication Type: Others
Murdoch Affiliation: School of Engineering and Information Technology
Publisher: Cornell University Library
Item Control Page Item Control Page


Downloads per month over past year