Optimal Packed String Matching

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2011

View graph of relations

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
StatePublished

Conference

ConferenceIARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
CountryIndia
CityMumbai
Period12/12/1114/12/11
NameLeibniz International Proceedings in Informatics (LIPIcs)
Number13
ISSN (Print)1868-8969

Bibliographical note

Licensed under Creative Commons License NC-ND.

CitationsWeb of Science® Times Cited: No match on DOI

Keywords

  • Bit parallelism, Space efficiency, Real time, String matching
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

Download statistics

No data available

ID: 6335068