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

DOI10.1016/j.jcss.2016.09.003zbMath1353.68225OpenAlexW2531235815MaRDI QIDQ340577

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

greatest common divisorabelian periodjumbled pattern matching

Mathematics Subject Classification ID

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

Related Items (4)

String Periods in the Order-Preserving Model ⋮ Finding patterns and periods in Cartesian tree matching ⋮ Regular Abelian Periods and Longest Common Abelian Factors on Run-Length Encoded Strings ⋮ String periods in the order-preserving model

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Abelian powers and repetitions in Sturmian words
• Indexing permutations for binary strings
• Sub-quadratic time and linear space data structures for permutation matching in binary strings
• Algorithms for computing abelian periods of words
• Avoiding Abelian squares in partial words
• Problems in between words and abelian words: \(k\)-abelian avoidability
• Binary jumbled pattern matching on trees and tree-like structures
• On shortest crucial words avoiding abelian powers
• A cyclic binary morphism avoiding abelian fourth powers
• A note on efficient computation of all abelian periods in a string
• 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
• Subquadratic-Time Algorithms for Abelian Stringology Problems
• Efficient Indexes for Jumbled Pattern Matching with Constant-Sized Alphabet
• Abelian pattern avoidance in partial words
• ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS
• Abelian Pattern Avoidance in Partial Words
• Clustered Integer 3SUM via Additive Combinatorics
• Fast Algorithms for Abelian Periods in Words and Greatest Common Divisor Queries
• AVOIDING ABELIAN POWERS IN BINARY WORDS WITH BOUNDED ABELIAN COMPLEXITY
• Efficient randomized pattern-matching algorithms
• A linear sieve algorithm for finding prime numbers
• Jewels of Stringology
• ABELIAN PRIMITIVE WORDS
• On Hardness of Jumbled Indexing
• Avoiding Abelian Powers in Partial Words
• Abelian squares are avoidable on 4 letters
• On the Asymptotic Abelian Complexity of Morphic Words

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