The
indexing problem is the one where a text is preprocessed and subsequent queries of the form: “Find all occurrences of pattern
P in the text” are answered in time proportional to the length of the query and the number of occurrences. In the
dictionary matching problem a set of patterns is preprocessed and subsequent queries of the form: “Find all occurrences of dictionary patterns in text
T” are answered in time proportional to the length of the text and the number of occurrences.
In this paper we present a uniform deterministic solution to both the indexing and the general dictionary matching problem
with one error. We preprocess the data in time O(n log2
n), where n is the text size in the indexing problem and the dictionary size in the dictionary matching problem. Our query time for the
indexing problem is O(mlog n log log n+ tocc), where m is the query string size and tocc is the number of occurrences.
Our query time for the dictionary matching problem is O(n log3
d log log d+ tocc), where n is the text size and d the dictionary size.