The position end-set tree: A small automaton for word recognition in biological sequences
Christophe M. Lefèvre, Joh‐E Ikeda · Computer applications in the biosciences · 1993
We consider the basic function which locates a specific string of symbols within a longer sequence. When one is expecting to do many substring searches it is worthwhile to build an auxiliary index to the sequence to aid in the search. We propose a method to generate a compact index that can be viewed as a small (partial) deterministic finite automaton recognizing the subword structure of a sequence. We present an algorithm for its construction on-line in linear time. Such a data structure permits the efficient localization of subwords in a sequence and can be used in the development of interactive sequence analysis software.