Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

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 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 and a skeleton...

Page 1

Download Results (CSV)