Abstract
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.
Original language | English |
---|---|
Title of host publication | IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011) |
Editors | Supratik Chakraborty, Amit Kumar |
Place of Publication | Dagstuhl, Germany |
Publisher | Schloss Dagstuhl-Leibniz-Zentrum fuer Informati |
Publication date | 2011 |
Pages | 423-432 |
ISBN (Print) | 978-3-939897-34-7 |
DOIs | |
Publication status | Published - 2011 |
Event | 31st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science - Mumbai, India Duration: 12 Dec 2011 → 14 Dec 2011 http://fsttcs.org/archives/2011/ |
Conference
Conference | 31st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science |
---|---|
Country/Territory | India |
City | Mumbai |
Period | 12/12/2011 → 14/12/2011 |
Internet address |
Series | Leibniz International Proceedings in Informatics |
---|---|
Number | 13 |
ISSN | 1868-8969 |
Bibliographical note
Licensed under Creative Commons License NC-ND.Keywords
- Bit parallelism
- Space efficiency
- Real time
- String matching