The factor automaton. (English) Zbl 1265.68092

Summary: This paper concerns searching substrings in a string using the factor automaton. The factor automaton is a deterministic finite automaton constructed to accept every substring of the given string. The nondeterministic factor automaton is used to achieve new operations on factor automata for searching in non-constant texts.


68Q45 Formal languages and automata
68P05 Data structures
Full Text: Link


[1] Crochemore M., Rytter W.: Text Algorithms, Chapter 6, Subword graphs. Oxford University Press, Oxford 1994 · Zbl 0844.68101
[2] Melichar B.: The construction of factor automata. Workshop’98, vol. 1, Czech Technical University, Prague 1997, pp. 189-190
[3] Šimánek M.: Operations on factor automaton. Workshop ’98, vol. 1, Czech Technical University, Prague 1997, pp. 207-208
[4] Šimánek M.: The factor automaton. Proceedings of the Prague Stringology Club Workshop’98, Czech Technical University Prague, 1998, pp. 102-106
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.