The Prague Stringology Conference 2003

Bořivoj Melichar and Milan Šimánek

Operation L-INSERT on Factor Automaton

Abstract:
The factor automaton is used for time-optimal searching for substrings in text. In general, if the text is changed the new factor automaton has to be constructed. When the text change is simple enough we can change the original factor automaton to reflect the changes of the text and save the time of the new factor automaton construction. This paper deals with operation L-INSERT and describes the algorithm modifying the factor automaton when a new symbol is prepended to the text. This algorithm can be also used for on-line backward construction of factor automaton.

Download paper: Article in PostScript Article in PDF
 PostScript   PDF