Fast algorithms for abelian periods in words and greatest common divisor queries

DOI10.1016/J.JCSS.2016.09.003zbMATH Open1353.68225OpenAlexW2531235815MaRDI QIDQ340577FDOQ340577

Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter

Publication date: 14 November 2016

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2013/3938/

zbMATH Keywords

abelian periodgreatest common divisorjumbled pattern matching

Mathematics Subject Classification ID

Data structures (68P05) Combinatorics on words (68R15) Algorithms on strings (68W32)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient randomized pattern-matching algorithms
• Jewels of Stringology
• Abelian powers and repetitions in Sturmian words
• AVOIDING ABELIAN POWERS IN BINARY WORDS WITH BOUNDED ABELIAN COMPLEXITY
• ABELIAN PRIMITIVE WORDS
• Efficient Indexes for Jumbled Pattern Matching with Constant-Sized Alphabet
• Algorithms for jumbled pattern matching in strings
• Clustered Integer 3SUM via Additive Combinatorics
• Fast Algorithms for Abelian Periods in Words and Greatest Common Divisor Queries
• Sub-quadratic time and linear space data structures for permutation matching in binary strings
• On Hardness of Jumbled Indexing
• A note on efficient computation of all abelian periods in a string
• Subquadratic-Time Algorithms for Abelian Stringology Problems
• Algorithms for computing abelian periods of words
• Abelian squares are avoidable on 4 letters
• Problems in between words and abelian words: \(k\)-abelian avoidability
• A cyclic binary morphism avoiding abelian fourth powers
• Long binary patterns are abelian 2-avoidable
• Binary jumbled string matching for highly run-length compressible texts
• Computing abelian complexity of binary uniform morphic words
• Abelian pattern avoidance in partial words
• Abelian Pattern Avoidance in Partial Words
• Indexing permutations for binary strings
• A linear sieve algorithm for finding prime numbers
• Avoiding Abelian Powers in Partial Words
• On the Asymptotic Abelian Complexity of Morphic Words
• Avoiding Abelian squares in partial words
• Binary jumbled pattern matching on trees and tree-like structures
• On shortest crucial words avoiding abelian powers

Cited In (5)

• Regular Abelian Periods and Longest Common Abelian Factors on Run-Length Encoded Strings
• String Periods in the Order-Preserving Model
• A note on easy and efficient computation of full abelian periods of a word
• Finding patterns and periods in Cartesian tree matching
• String periods in the order-preserving model

This page was built for publication: Fast algorithms for abelian periods in words and greatest common divisor queries

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