Optimal Packed String Matching

Oren Ben-Kiki, Philip Bille, Dany Breslauer, Leszek Gasieniec, Roberto Grossi, Oren Weimann

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    392 Downloads (Pure)

    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 languageEnglish
    Title of host publicationIARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)
    EditorsSupratik Chakraborty, Amit Kumar
    Place of PublicationDagstuhl, Germany
    PublisherSchloss Dagstuhl-Leibniz-Zentrum fuer Informati
    Publication date2011
    Pages423-432
    ISBN (Print)978-3-939897-34-7
    DOIs
    Publication statusPublished - 2011
    Event31st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science - Mumbai, India
    Duration: 12 Dec 201114 Dec 2011
    http://fsttcs.org/archives/2011/

    Conference

    Conference31st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
    CountryIndia
    CityMumbai
    Period12/12/201114/12/2011
    Internet address
    SeriesLeibniz International Proceedings in Informatics
    Number13
    ISSN1868-8969

    Bibliographical note

    Licensed under Creative Commons License NC-ND.

    Keywords

    • Bit parallelism
    • Space efficiency
    • Real time
    • String matching

    Fingerprint Dive into the research topics of 'Optimal Packed String Matching'. Together they form a unique fingerprint.

    Cite this