For the exact search of a pattern of length m in a database of n strings of (arbitrary) length
the trie data structure allows an optimal lookup time of O\left(m\right). If errors are allowed
between the pattern and the database strings, no such structure with reasonable size is
known. Using a trie some work can be saved and running times superior to the comparison
with every string in the database can be achieved. We investigate a comparison-based
model where “errors” and “matches” are defined between pairs of characters. When …

For the exact search of a pattern of length m in a database of n strings the trie data structure
allows an optimal lookup time of O (m). If mismatches are allowed between the pattern and
the database strings, no such structure with reasonable size is known. Some work can be
saved using a trie and running times superior to the comparison with every string in the
database can be achieved. We investigate a comparison-based model where matches and
mismatches are defined between pairs of characters. When comparing two characters, let q …