Efficient validation and construction of border arrays
Jean-Pierre Duval, Thierry Lecroq, Arnaud Lefebvre · 2006
In this article we present an on-line linear time and space algorithm to check if an integer array f is the border array of at least one string w built on a bounded or unbounded size alphabet Σ. We first show some relations between the border array of some string w and the skeleton of the DFA recognizing Σ ∗ ·w, independently of the explicit knowledge of w. This enables us to design algorithms for validating and generating border arrays that outperform existing ones [4, 3]. The validating algorithm lowers the delay (time spent on one element of the array) from O(|w|) to O(min{|Σ|, |w|}) comparing to algorithms in [4, 3]. Finally we give some results on the numbers of distinct border arrays on some alphabet sizes. 1