\(k\)-abelian pattern matching

DOI10.1016/j.jda.2015.05.004zbMath1336.68314OpenAlexW436182755MaRDI QIDQ491150

Dirk Nowotka, Thorsten Ehlers, Robert Mercaş, Florin Manea

Publication date: 24 August 2015

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2015.05.004

zbMATH Keywords

algorithmspattern matchingcombinatorics on wordsjumbled pattern matchingabelian equivalences

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Related Items (4)

Absent Subsequences in Words ⋮ On cardinalities of \(k\)-abelian equivalence classes ⋮ Popping Superbubbles and Discovering Clumps: Recent Developments in Biological Sequence Analysis ⋮ k-Abelian Equivalence and Rationality

Cites Work

• Unnamed Item
• Unnamed Item
• On a generalization of abelian equivalence and complexity of infinite words
• Problems in between words and abelian words: \(k\)-abelian avoidability
• Computing suffix links for suffix trees and arrays
• An optimal algorithm for computing the repetitions in a word
• Preserving order in a forest in less than logarithmic time and linear space
• On the computational power of pushdown automata
• Binary Jumbled Pattern Matching on Trees and Tree-Like Structures
• Efficient Indexes for Jumbled Pattern Matching with Constant-Sized Alphabet
• Weighted Ancestors in Suffix Trees
• k-Abelian Pattern Matching
• Variations of the Morse-Hedlund Theorem for k-Abelian Equivalence
• Local Squares, Periodicity and Finite Automata
• Simple Real-Time Constant-Space String Matching
• Fine and Wilf’s Theorem for k-Abelian Periods
• Linear work suffix array construction
• Constructing Efficient Dictionaries in Close to Sorting Time
• Algorithms on Strings, Trees and Sequences
• 3-Abelian Cubes Are Avoidable on Binary Alphabets

This page was built for publication: \(k\)-abelian pattern matching