Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

Computing covers using prefix tables

Alatabbi, A., Sohel Rahman, M. and Smyth, W.F. (2015) Computing covers using prefix tables. Discrete Applied Mathematics, 212 . pp. 2-9.

[img]
Preview
PDF - Authors' Version
Download (622kB) | Preview
Link to Published Version: http://dx.doi.org/10.1016/j.dam.2015.05.019
*Subscription may be required

Abstract

An indeterminate string x=x[1..n] on an alphabet ΣΣ is a sequence of nonempty subsets of ΣΣ; x is said to be regular if every subset is of size one. A proper substring u of regular x is said to be a cover of x iff for every i∈1..ni∈1..n, an occurrence of u in x includes x[i]. The cover array γ=γ[1..n] of x is an integer array such that γ[i] is the longest cover of x[1..i]. Fifteen years ago a complex, though nevertheless linear-time, algorithm was proposed to compute the cover array of regular x based on prior computation of the border array of x. In this paper we first describe a linear-time algorithm to compute the cover array of regular x based on the prefix table of x. We then extend this result to indeterminate strings.

Item Type: Journal Article
Murdoch Affiliation(s): School of Engineering and Information Technology
Publisher: Elsevier BV
Copyright: © 2015 Elsevier B.V.
URI: http://researchrepository.murdoch.edu.au/id/eprint/27326
Item Control Page Item Control Page

Downloads

Downloads per month over past year