2026-07-23T20:02:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3355 2024-03-06T10:34:07Z ddc:004 open_access

Optimal Packed String Matching Ben-Kiki, Oren Bille, Philip Breslauer, Dany Gasieniec, Leszek Grossi, Roberto Weimann, Oren String matching bit parallelism real time space efficiency In the packed string matching problem, each machine word accomodates alpha characters, thus an n-character text occupies n/alpha memory words. We extend the Crochemore-Perrin constant-space O(n)-time string matching algorithm to run in optimal O(n/alpha) time and even in real-time, achieving a factor alpha 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Oren Ben-Kiki and Philip Bille and Dany Breslauer and Leszek Gasieniec and Roberto Grossi and Oren Weimann 2011 Is Part Of LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2011.423 urn:nbn:de:0030-drops-33558 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.423 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode