Efficient indexes for jumbled pattern matching with constant-sized alphabet

DOI10.1007/S00453-016-0140-0MaRDI QIDQ524375zbMATH OpenOpenAlexWikidataFDO

Authors Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter

Publication date 2 May 2017

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-016-0140-0

zbMATH Keywords

jumbled pattern matchingabelian equivalencejumbled indexinghistogram indexing

Mathematics Subject Classification ID

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

Recommendations

• Efficient indexes for jumbled pattern matching with constant-sized alphabet
• Efficient indexes for the positional pattern matching problem and two related problems over small alphabets
• Fast and simple jumbled indexing for binary run-length encoded strings
• On approximate jumbled pattern matching in strings
• Algorithms for jumbled pattern matching in strings
• scientific article; zbMATH DE number 2011852
• Efficient randomized pattern-matching algorithms

Cites work

• Algorithms for jumbled pattern matching in strings
• Binary jumbled pattern matching on trees and tree-like structures
• Clustered Integer 3SUM via Additive Combinatorics
• Constrained multilinear detection and generalized graph motifs
• Efficient indexes for jumbled pattern matching with constant-sized alphabet
• Fast construction of wavelet trees
• Faster all-pairs shortest paths via circuit complexity
• Indexing permutations for binary strings
• Necklaces, convolutions, and \(X+Y\)
• On approximate jumbled pattern matching in strings
• On hardness of jumbled indexing
• On the relationship between histogram indexing and block-mass indexing
• Scaled and permuted string matching
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Sub-quadratic time and linear space data structures for permutation matching in binary strings
• Upper and lower bounds for finding connected motifs in vertex-colored graphs
• Wavelet trees meet suffix trees

Cited in

(14)

• Bubble-flip -- a new generation algorithm for prefix normal words
• New algorithms for binary jumbled pattern matching
• Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
• Efficient indexes for jumbled pattern matching with constant-sized alphabet
• On approximate jumbled pattern matching in strings
• Fast and simple jumbled indexing for binary run-length encoded strings
• A Linear Size Index for Approximate Pattern Matching
• Efficient indexes for the positional pattern matching problem and two related problems over small alphabets
• On hardness of jumbled indexing
• CSA++: Fast Pattern Search for Large Alphabets
• Real-Time Streaming Multi-Pattern Search for Constant Alphabet
• Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings
• Algorithms for jumbled pattern matching in strings
• Indexed geometric jumbled pattern matching

This page was built for publication: Efficient indexes for jumbled pattern matching with constant-sized alphabet

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