EFFICIENT VALIDATION AND CONSTRUCTION OF BORDER ARRAYS AND VALIDATION OF STRING MATCHING AUTOMATA

We present an on-line linear time and space algorithm tocheck if an integer array f is the border array of at least one string wbuilt on a bounded or unbounded size alphabet Σ. First of all, we showa bijection between the border array of a string w and the skeleton ofthe DFA recognizing Σw , called a string matching automaton (SMA).Different strings can have the same border array but the originality ofthe presented method is that the correspondence between a border ar-ray and a skeleton of SMA is independent from the underlying strings.This enables to design algorithms for validating and generating borderarrays that outperform existing ones. The validating algorithm low-ers the delay (maximal number of comparisons on one element of thearray) from O ( |w |)to1+min{| Σ|, 1+log2|w |} compared to existingalgorithms. We then give results on the numbers of distinct borderarrays depending on the alphabet size. We also present an algorithmthat checks if a given directed unlabeled graph G is the skeleton of aSMA on an alphabet of size s in linear time. Along the process thealgorithm can build one string w for which G is the SMA skeleton