Computing covers using prefix tables

Abstract: An emph{indeterminate string}

x = x [1.. n]

on an alphabet

S i g m a

is a sequence of nonempty subsets of

S i g m a

;

x

is said to be emph{regular} if every subset is of size one. A proper substring

u

of regular

x

is said to be a emph{cover} of

x

iff for every

i i n 1.. n

, an occurrence of

u

in

x

includes

x [i]

. The emph{cover array}

g a m m a = g a m m a [1.. n]

of

x

is an integer array such that

g a m m a [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 string

x

based on the prefix table of

x

. We then extend this result to indeterminate strings.

Recommendations

Cites Work

Cited In (15)

This page was built for publication: Computing covers using prefix tables