License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2011.423
URN: urn:nbn:de:0030-drops-33558
Go to the corresponding LIPIcs Volume Portal

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

Optimal Packed String Matching

37.pdf (0.5 MB)


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.

BibTeX - Entry

  author =	{Oren Ben-Kiki and Philip Bille and Dany Breslauer and Leszek Gasieniec and Roberto Grossi and Oren Weimann},
  title =	{{Optimal Packed String Matching }},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{423--432},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Supratik Chakraborty and Amit Kumar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-33558},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.423},
  annote =	{Keywords: String matching, bit parallelism, real time, space efficiency}

Keywords: String matching, bit parallelism, real time, space efficiency
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)
Issue Date: 2011
Date of publication: 01.12.2011

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI