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

DOI10.1016/j.jda.2011.12.011zbMath1247.68332OpenAlexW2004654138MaRDI QIDQ450552

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

independent setmodular decompositionfixed-parameter tractabilityhereditary class of graphs

Mathematics Subject Classification ID

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

Related Items (1)

Streaming dictionary matching with mismatches

Uses Software

• MPSCAN

Cites Work

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

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