Fast Searching in Packed Strings

DOI10.1007/978-3-642-02441-2_11MaRDI QIDQ3637108zbMATH OpenOpenAlexFDO

Authors Philip Bille

Publication date 7 July 2009

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0907.3135

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Abstract: 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., 1977] 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 $mleqn$ be the lengths $P$ and $Q$, respectively, and let $sigma$ denote the size of the alphabet. On a standard unit-cost word-RAM with logarithmic word size we present an algorithm using time ${\displaystyle }$ Oleft(frac{n}{log_sigma n} + m + occ ight). ${\displaystyle }$ 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/lo{g}_{s}igman)$ our algorithm is optimal since any algorithm must spend at least $Omega(frac(n+m)logsigmalogn+occ)=Omega(fracnlo{g}_{s}igman+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.

Recommendations

• Fast searching in packed strings
• Optimal packed string matching
• Average optimal string matching in packed strings
• Towards optimal packed string matching
• Worst-case efficient single and multiple string matching on packed texts in the word-RAM model

Cites work

• A fast string searching algorithm
• A faster algorithm computing string edit distances
• A Four Russians algorithm for regular expression pattern matching
• A Subquadratic Algorithm for Approximate Regular Expression Matching
• Accelerating Boyer Moore Searches on Binary Texts
• Algorithms on Strings, Trees and Sequences
• Efficient randomized pattern-matching algorithms
• Efficient variants of the backward-oracle-matching algorithm
• Fast Pattern Matching in Strings
• scientific article; zbMATH DE number 140461 (Why is no real title available?)
• scientific article; zbMATH DE number 1490000 (Why is no real title available?)
• scientific article; zbMATH DE number 1754502 (Why is no real title available?)
• scientific article; zbMATH DE number 742992 (Why is no real title available?)
• scientific article; zbMATH DE number 3340123 (Why is no real title available?)
• Let sleeping files lie: Pattern matching in Z-compressed files.
• Shift-or string matching with super-alphabets

Cited in

(18)

• Validating the Knuth-Morris-Pratt failure function, fast and online
• Compact recognizers of episode sequences
• Squares, cubes, and time-space efficient string searching
• Towards optimal packed string matching
• The complexity of searching a sorted array of strings
• Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing
• Optimal packed string matching
• Worst case efficient single and multiple string matching in the RAM model
• Validating the Knuth-Morris-Pratt failure function, fast and online
• Fast and flexible packed string matching
• Efficient string matching on packed texts
• scientific article; zbMATH DE number 1982178 (Why is no real title available?)
• Worst-case efficient single and multiple string matching on packed texts in the word-RAM model
• Average optimal string matching in packed strings
• Deterministic indexing for packed strings
• Fast Packed String Matching for Short Patterns
• Fast convolutions of packed strings and pattern matching with wildcards
• Fast searching in packed strings

This page was built for publication: Fast Searching in Packed Strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3637108)