On approximate jumbled pattern matching in strings

DOI10.1007/s00224-011-9344-5zbMath1253.68372OpenAlexW2074382201MaRDI QIDQ692932

Zsuzsanna Lipták, Gabriele Fici, Péter Burcsi, Ferdinando Cicalese

Publication date: 6 December 2012

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-011-9344-5

zbMATH Keywords

pattern matchingstring algorithmsaverage case analysisapproximate searchParikh vectorspermuted strings

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Algorithms on strings (68W32)

Related Items (18)

Permuted scaled matching ⋮ Computing abelian complexity of binary uniform morphic words ⋮ Binary jumbled pattern matching on trees and tree-like structures ⋮ On the relationship between histogram indexing and block-mass indexing ⋮ Dyck Words, Lattice Paths, and Abelian Borders ⋮ Sub-quadratic time and linear space data structures for permutation matching in binary strings ⋮ Finding patterns and periods in Cartesian tree matching ⋮ Approximating the maximum consecutive subsums of a sequence ⋮ Unnamed Item ⋮ Binary jumbled string matching for highly run-length compressible texts ⋮ Algorithms for computing abelian periods of words ⋮ Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings ⋮ Efficient indexes for jumbled pattern matching with constant-sized alphabet ⋮ Generating a Gray code for prefix normal words in amortized polylogarithmic time per word ⋮ On prefix normal words and prefix normal forms ⋮ Improved online algorithms for jumbled matching ⋮ On infinite prefix normal words ⋮ Cartesian Tree Matching and Indexing

Cites Work

• Unnamed Item
• Unnamed Item
• Indexing permutations for binary strings
• Sub-quadratic time and linear space data structures for permutation matching in binary strings
• Scaled and permuted string matching
• A fast and simple algorithm for the money changing problem
• The generalized Banach match-box problem: Application in disc storage management
• Algorithmic complexity of protein identification: Combinatorics of weighted strings
• Efficient text fingerprinting via Parikh mapping
• ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS
• Compressed representations of sequences and full-text indexes
• ERRATUM: "INDUCED ELECTROSTATIC SELF-INTERACTION IN THE SPACE–TIME OF A GLOBAL MONOPOLE WITH INNER STRUCTURE"
• A Stochastic Allocation Problem
• Fast Pattern Matching in Strings
• Optimal storage allocation for serial files
• Necklaces, Convolutions, and X + Y

This page was built for publication: On approximate jumbled pattern matching in strings