Efficient indexes for the positional pattern matching problem and two related problems over small alphabets

[[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].[[fileno]]2030215030026[[department]]資訊工程學