Fast searching in packed strings

DOI10.1016/J.JDA.2010.09.003zbMath1216.68121OpenAlexW1914023312MaRDI QIDQ533408

Philip Bille

Publication date: 3 May 2011

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2010.09.003

zbMATH Keywords

string matchingKnuth-Morris-Pratt algorithmword RAM

Mathematics Subject Classification ID

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

Related Items (4)

Fast and flexible packed string matching ⋮ Towards optimal packed string matching ⋮ Approximate pattern matching with \(k\)-mismatches in packed text ⋮ Fast Convolutions of Packed Strings and Pattern Matching with Wildcards

Cites Work

• Let sleeping files lie: Pattern matching in Z-compressed files.
• Shift-or string matching with super-alphabets
• A faster algorithm computing string edit distances
• A fast string searching algorithm
• Accelerating Boyer Moore Searches on Binary Texts
• Faster Regular Expression Matching
• EFFICIENT VARIANTS OF THE BACKWARD-ORACLE-MATCHING ALGORITHM
• Efficient randomized pattern-matching algorithms
• Efficient string matching
• Fast Pattern Matching in Strings
• Algorithms on Strings, Trees and Sequences
• A Four Russians algorithm for regular expression pattern matching
• A Subquadratic Algorithm for Approximate Regular Expression Matching
• Programming Techniques: Regular expression search algorithm
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Fast searching in packed strings