Fast circular dictionary-matching algorithm

DOI10.1017/S0960129515000134MaRDI QIDQ2971059zbMATH OpenOpenAlexFDO

Authors Tanver Athar, Carl Barton, Widmer Bland, Jia Gao, Costas S. Iliopoulos, Chang Liu, Solon P. Pissis

Publication date 4 April 2017

Published in Mathematical Structures in Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.1017/s0960129515000134

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• Bit-Parallel Approximate Matching of Circular Strings with k Mismatches
• Average-case optimal approximate circular string matching
• Efficient algorithm for circular Burrows-Wheeler transform
• Circular pattern matching with \(k\) mismatches
• Circular pattern matching with k mismatches

Cites work

• Algorithms on Strings, Trees and Sequences
• Approximate string matching using compressed suffix arrays
• Average-case optimal approximate circular string matching
• Average-optimal string matching
• Compressed indexes for dynamic text collections
• Construction of Aho Corasick automaton in linear time for integer alphabets
• Efficient string matching
• Faster compressed dictionary matching
• scientific article; zbMATH DE number 2183071 (Why is no real title available?)
• Indexing Circular Patterns
• Inducing the LCP-array
• Partial-Match Retrieval Algorithms
• Space-efficient construction algorithm for the circular suffix tree
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• Succinct Dictionary Matching with No Slowdown
• Succinct indexes for circular patterns
• Suffix Arrays: A New Method for On-Line String Searches
• The longest common extension problem revisited and applications to approximate string searching

Cited in

(12)

• A simple, fast, filter-based algorithm for circular sequence comparison
• Fast approximate matching of words against a dictionary
• Parameterized dictionary matching and recognition with one gap
• Average-case optimal approximate circular string matching
• Efficient algorithm for circular Burrows-Wheeler transform
• Searching and indexing circular patterns
• Finding optimal alignment and consensus of circular strings
• Quasi-Linear-Time Algorithm for Longest Common Circular Factor
• Real-Time Streaming Multi-Pattern Search for Constant Alphabet
• Quasi-linear-time algorithm for a longest common circular factor
• Compressed dictionary matching on run-length encoded strings
• Compressed dictionary matching on run-length encoded strings

This page was built for publication: Fast circular dictionary-matching algorithm

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