The Prague Stringology Conference 2009
Maxime Crochemore and Laura Giambruno
On-line construction of a small automaton for a finite set of words
| Abstract: |
| In this paper we describe a ``light'' algorithm for the on-line construction of a small automaton recognising a finite set of words. The algorithm runs in linear time. We carried out good experimental results on the suffixes of a text, showing how this automaton is small. For the suffixes of a text, we propose a modified construction that leads to an even smaller automaton. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |