Page 1

Displaying 1 – 3 of 3

Showing per page

Efficient validation and construction of border arrays and validation of string matching automata

Jean-Pierre Duval, Thierry Lecroq, Arnaud Lefebvre (2009)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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 Σ . First of all, we show a bijection between the border array of a string w and the skeleton of the DFA recognizing Σ * w , 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 and a skeleton of SMA...

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

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 Σ. First of all, we show a bijection between the border array of a string w 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 and a...

Currently displaying 1 – 3 of 3

Page 1