Skip to content


Algorithms based on Automata

Also automata play a very important role in the design of efficient string matching algorithms. For instance, the Deterministic Finite Automaton Matcher [31] was one of the first linear-time solutions, whereas the Backward-DAWG-Matching algorithm [35] reached the optimal O(nlogσmm)O(\frac{n \log_{σ} m}{m}) lower bound time complexity on the average. Both of them are based on finite automata; in particular, they respectively simulate a deterministic automaton for the language ΣpΣ^∗p and the deterministic suffix automaton of the reverse of pp.

The efficiency of string matching algorithms depends on the underlying automaton used for recognizing the pattern pp and on the encoding used for simulating it.