King's College London

Research portal

Computing covers using prefix tables

Research output: Contribution to journalArticlepeer-review

Ali Alatabbi, M. Sohel Rahman, W. F. Smyth

Original languageEnglish
JournalDISCRETE APPLIED MATHEMATICS
DOIs
Accepted/In press6 Jun 2015

Bibliographical note

Not freely accessible but may have access through institution

King's Authors

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..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.

View graph of relations

© 2020 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454