Conference paper
Optimal Packed String Matching
Intel Research and Development Center1
Algorithms and Logic, Department of Informatics and Mathematical Modeling, Technical University of Denmark2
Department of Informatics and Mathematical Modeling, Technical University of Denmark3
University of Haifa4
University of Liverpool5
Università di Pisa6
In the packed string matching problem, each machine word accommodates – characters, thus an n-character text occupies n/– memory words. We extend the Crochemore-Perrin constantspace O(n)-time string matching algorithm to run in optimal O(n/–) time and even in real-time, achieving a factor – speedup over traditional algorithms that examine each character individually.
Our solution can be efficiently implemented, unlike prior theoretical packed string matching work. We adapt the standard RAM model and only use its AC0 instructions (i.e., no multiplication) plus two specialized AC0 packed string instructions. The main string-matching instruction is available in commodity processors (i.e., Intel’s SSE4.2 and AVX Advanced String Operations); the other maximal-suffix instruction is only required during pattern preprocessing.
In the absence of these two specialized instructions, we propose theoretically-efficient emulation using integer multiplication (not AC0) and table lookup.
Language: | English |
---|---|
Publisher: | Schloss Dagstuhl-Leibniz-Zentrum fuer Informati |
Year: | 2011 |
Pages: | 423-432 |
Proceedings: | 31st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science |
Series: | Leibniz International Proceedings in Informatics |
ISBN: | 3939897345 and 9783939897347 |
ISSN: | 18688969 |
Types: | Conference paper |
DOI: | 10.4230/LIPIcs.FSTTCS.2011.423 |
ORCIDs: | Bille, Philip |