Advertisement
Published in:
2010 | OriginalPaper | Chapter
Efficient Indexes for the Positional Pattern Matching Problem and Two Related Problems over Small Alphabets
Authors : Chih-Chiang Yu, Biing-Feng Wang, Chung-Chin Kuo
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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].