The Prague Stringology Conference 2002

Jean-Pierre Duval, Thierry Lecroq and Arnaud Lefebvre

Border Array on Bounded Alphabet

In this article we present an on-line linear time algorithm, to check if an integer array f is a border array of some string x built on a bounded size alphabet. Furthermore if f is a border array we are able to build, on-line and in linear time, a string x on a minimal size alphabet for which f is the border array.

Download paper: Article in PostScript Article in PDF
 PostScript   PDF