From nondeterministic suffix automaton to lazy suffix tree

摘要: Given two strings, a pattern P of length m and text T n over some alphabet Σ size σ, we consider the exact string matching problem, i.e. want to report all occurrences in T. The well-known Backward-Nondeterministic-DAWG-Matching (BNDM) algorithm is one most efficient for short moderate patterns. In this paper – as prelude take underlying nondeterministic suffix automaton apply it instead pattern. resulting surprisingly simple, relatively patterns small sizes practice. We then show how can be easily adapted construct tree lazy manner. Both algorithms are if static but given on-line (without possibility batch queries). discuss various variants algorithms, conclude with experimental results.