ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS

DOI10.1142/S0129054112400175zbMath1246.68273MaRDI QIDQ2909200

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

Publication date: 30 August 2012

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

pattern matchingstring algorithmsaverage case analysisParikh vectorspermuted strings

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10) Combinatorics on words (68R15) Computing methodologies for text processing; mathematical typography (68U15) Algorithms on strings (68W32)

Related Items

Circular Sequence Comparison with q-grams, Weighted prefix normal words: mind the gap, Permuted scaled matching, Computing abelian complexity of binary uniform morphic words, Fast algorithms for abelian periods in words and greatest common divisor queries, The graph motif problem parameterized by the structure of the input graph, Binary jumbled pattern matching on trees and tree-like structures, 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, Unnamed Item, Binary jumbled string matching for highly run-length compressible texts, Fast algorithms for single and multiple pattern Cartesian tree matching, Abelian borders in binary words, 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, On approximate jumbled pattern matching in strings, 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, Bubble-flip -- a new generation algorithm for prefix normal words

Cites Work

• Unnamed Item
• Scaled and permuted string matching
• Algorithmic complexity of protein identification: Combinatorics of weighted strings
• Efficient text fingerprinting via Parikh mapping
• A fast string searching algorithm
• The Boyer–Moore–Galil String Searching Strategies Revisited
• Fast Pattern Matching in Strings