Efficient validation and construction of border arrays and validation of string matching automata
Jean-Pierre Duval, Thierry Lecroq, Arnaud Lefebvre (2008)
RAIRO - Theoretical Informatics and Applications
Similarity:
We present an on-line linear time and space algorithm to check if an integer array is the border array of at least one string built on a bounded or unbounded size alphabet . First of all, we show a bijection between the border array of a string and the skeleton of the DFA recognizing Σ*ω, called a string matching automaton (SMA). Different strings can have the same border array but the originality of the presented method is that the correspondence between a border array...