TY - GEN
T1 - Constant-time word-size string matching
AU - Breslauer, Dany
AU - Ga̧sieniec, Leszek
AU - Grossi, Roberto
PY - 2012
Y1 - 2012
N2 - We present a novel string-matching algorithm that requires constant time for text scanning in an unusual model where (a) the input pattern and text are each packed into a single word, (b) the output is a one word bit-mask identifying the pattern occurrences in the text, and (c) there are constant-time arithmetic, bitwise, and shift instructions that operate on words whose size is proportional to the arbitrarily long input length. Our bit-parallelism techniques build upon and also greatly simplify existing parallel random access machine algorithms by using two "simple structure" rather than "small size" deterministic samples, i.e., one deterministic sample is very small (size two), while the other is a potentially very long prefix of the pattern. Pattern preprocessing takes time proportional to the word size. Our results also establish, by recent reductions, new bounds for the packed string matching problem.
AB - We present a novel string-matching algorithm that requires constant time for text scanning in an unusual model where (a) the input pattern and text are each packed into a single word, (b) the output is a one word bit-mask identifying the pattern occurrences in the text, and (c) there are constant-time arithmetic, bitwise, and shift instructions that operate on words whose size is proportional to the arbitrarily long input length. Our bit-parallelism techniques build upon and also greatly simplify existing parallel random access machine algorithms by using two "simple structure" rather than "small size" deterministic samples, i.e., one deterministic sample is very small (size two), while the other is a potentially very long prefix of the pattern. Pattern preprocessing takes time proportional to the word size. Our results also establish, by recent reductions, new bounds for the packed string matching problem.
UR - http://www.scopus.com/inward/record.url?scp=84863105850&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84863105850&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-31265-6_7
DO - 10.1007/978-3-642-31265-6_7
M3 - Conference contribution
AN - SCOPUS:84863105850
SN - 9783642312649
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 83
EP - 96
BT - Combinatorial Pattern Matching - 23rd Annual Symposium, CPM 2012, Proceedings
T2 - 23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012
Y2 - 3 July 2012 through 5 July 2012
ER -