Worst-case efficient single and multiple string matching on packed texts in the word-RAM model

DOI10.1016/J.JDA.2011.12.011MaRDI QIDQ450552zbMATH OpenOpenAlexFDO

Authors Djamal Belazzougui

Publication date 13 September 2012

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

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

zbMATH Keywords

modular decompositionfixed-parameter tractabilityindependent sethereditary class of graphs

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Recommendations

• Worst case efficient single and multiple string matching in the RAM model
• Average optimal string matching in packed strings
• Fast Searching in Packed Strings
• Fast searching in packed strings
• Constant-time word-size string matching

Cites work

• scientific article; zbMATH DE number 1688373 (Why is no real title available?)
• scientific article; zbMATH DE number 801745 (Why is no real title available?)
• scientific article; zbMATH DE number 3340123 (Why is no real title available?)
• A fast string searching algorithm
• Algorithms on Strings
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Design and implementation of an efficient priority queue
• Efficient string matching
• Fast Pattern Matching in Strings
• Fast Searching in Packed Strings
• Filtering Search: A New Approach to Query-Answering
• Indexing text using the Ziv--Lempel trie
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Optimal packed string matching
• Sorting in linear time?
• Speeding up two string-matching algorithms
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Succinct Dictionary Matching with No Slowdown
• Suffix Arrays: A New Method for On-Line String Searches
• Surpassing the information theoretic bound with fusion trees
• The Complexity of Pattern Matching for a Random String
• The string B-tree

Cited in

(8)

• Streaming dictionary matching with mismatches
• Worst case efficient single and multiple string matching in the RAM model
• Fast searching in packed strings
• Predecessor on the Ultra-Wide Word RAM
• Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing
• Average optimal string matching in packed strings
• Fast Searching in Packed Strings
• Constant-time word-size string matching

Describes a project that uses

Uses Software

• MPSCAN

This page was built for publication: Worst-case efficient single and multiple string matching on packed texts in the word-RAM model

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