zbMATH — the first resource for mathematics

Factor oracle: A new structure for pattern matching. (English) Zbl 0964.68078
Pavelka, Jan (ed.) et al., SOFSEM ’99: Theory and practice of informatics. 26th conference on Current trends in theory and practice of informatics. Milovy, Czech Republic, November 27-December 4, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1725, 295-310 (1999).
Summary: We introduce a new automaton on a word \(p\), sequence of letters taken in an alphabet \(\Sigma\), that we call factor oracle. This automaton is acyclic, recognizes at least the factors of \(p\), has \(m+ 1\) states and a linear number of transitions. We give an on-line construction to build it. We use this new structure in string matching algorithms that we conjecture optimal according to the experimental results. These algorithms are as efficient as the ones that already exist using less memory and being more easy to implement.
For the entire collection see [Zbl 0931.00042].

68Q45 Formal languages and automata
factor oracle