Abstract
In this paper, we study the following three variants of the classical text indexing problem over small alphabets: the positional pattern matching problem, the position-restricted pattern matching problem, and the indexing version of the variable-length don't care pattern matching problem. Let n be the length of the text, p be the length of a query pattern, and ∑ be the alphabet. Assume that |∑| = O(polylog(n)). For the first and third problems, we present O(n)-word indexes with O(p) query time. For the second problem, we show that each query can be answered in O(n log ε n) space and O(p + occ) time, or in O(n) space and O(p + occ log ε n) time, where occ is the number of outputs. When the alphabet size is O(polylog(n)), the indexes presented in this paper improve the results in [6, 10, 11, 22]. © 2010 Springer-Verlag.