The Prague Stringology Club Workshop '98
Implementation of DAWG
| Abstract: |
| Let T be a text over a fixed alphabet A. Then an automaton can be created in a linear time that accepts all substrings that occur in text T. The ratio of the size of the implementation of this automaton (factor automaton, DAWG) and of the input text is in usual cases 14:1. This paper shows a method of implementing DAWG that reduces this ratio down to 4:1 while preserving good qualities of the automaton, which is linear time of its construction with respect to the length of the input text and linear time of checking that a pattern is present in the text with respect to the length of the pattern. |
| Download paper: |  |
 |
| PostScript |