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

DOI10.1016/J.JDA.2011.12.011zbMATH Open1247.68332OpenAlexW2004654138MaRDI QIDQ450552FDOQ450552

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)

Cites Work

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

Cited In (3)

• Streaming dictionary matching with mismatches
• Predecessor on the Ultra-Wide Word RAM
• Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing

Uses Software

• MPSCAN

   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 👍 👎

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)