Fast searching in packed strings

Publication: Research - peer-reviewJournal article – Annual report year: 2011

View graph of relations

Given strings P and Q the (exact) string matching problem is to find all positions of substrings in Q matching P. The classical Knuth–Morris–Pratt algorithm [SIAM J. Comput. 6 (2) (1977) 323–350] solves the string matching problem in linear time which is optimal if we can only read one character at the time. However, most strings are stored in a computer in a packed representation with several characters in a single word, giving us the opportunity to read multiple characters simultaneously. In this paper we study the worst-case complexity of string matching on strings given in packed representation. Let m⩽n be the lengths P and Q, respectively, and let σ denote the size of the alphabet. On a standard unit-cost word-RAM with logarithmic word size we present an algorithm using timeO(nlogσn+m+occ). Here occ is the number of occurrences of P in Q. For m=o(n) this improves the O(n) bound of the Knuth–Morris–Pratt algorithm. Furthermore, if m=O(n/logσn) our algorithm is optimal since any algorithm must spend at least Ω((n+m)logσlogn+occ)=Ω(nlogσn+occ) time to read the input and report all occurrences. The result is obtained by a novel automaton construction based on the Knuth–Morris–Pratt algorithm combined with a new compact representation of subautomata allowing an optimal tabulation-based simulation.
Original languageEnglish
JournalJournal of Discrete Algorithms (Amsterdam)
Publication date2011
Volume9
Issue1
Pages49-56
ISSN1570-8667
DOIs
StatePublished
CitationsWeb of Science® Times Cited: No match on DOI

Keywords

  • String matching, Word RAM, Knuth–Morris–Pratt algorithm
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

ID: 6243833