Fast searching in packed strings

DOI10.1016/j.jda.2010.09.003zbMath1216.68121MaRDI 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 matching; Knuth-Morris-Pratt algorithm; word RAM

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68P10: Searching and sorting

68Q45: Formal languages and automata

68W32: Algorithms on strings

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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