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.
|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 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
|Conference||31st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science|
|Period||12/12/2011 → 14/12/2011|
|Series||Leibniz International Proceedings in Informatics|
Bibliographical noteLicensed under Creative Commons License NC-ND.
- Bit parallelism
- Space efficiency
- Real time
- String matching