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

DOI10.1016/J.JCSS.2016.09.003MaRDI QIDQ340577zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Fast algorithms for abelian periods in words and greatest common divisor queries
• Algorithms for computing abelian periods of words
• A note on easy and efficient computation of full abelian periods of a word
• Fast computation of abelian runs
• Identifying all abelian periods of a string in quadratic time and relevant problems

Cites work

• scientific article; zbMATH DE number 3162927 (Why is no real title available?)
• scientific article; zbMATH DE number 5605094 (Why is no real title available?)
• scientific article; zbMATH DE number 3523640 (Why is no real title available?)
• scientific article; zbMATH DE number 3296252 (Why is no real title available?)
• scientific article; zbMATH DE number 3375509 (Why is no real title available?)
• A cyclic binary morphism avoiding abelian fourth powers
• A linear sieve algorithm for finding prime numbers
• A note on efficient computation of all abelian periods in a string
• AVOIDING ABELIAN POWERS IN BINARY WORDS WITH BOUNDED ABELIAN COMPLEXITY
• Abelian pattern avoidance in partial words
• Abelian pattern avoidance in partial words
• Abelian powers and repetitions in Sturmian words
• Abelian primitive words
• Abelian squares are avoidable on 4 letters
• Algorithms for computing abelian periods of words
• Algorithms for jumbled pattern matching in strings
• Avoiding Abelian squares in partial words
• Avoiding abelian powers in partial words
• Binary jumbled pattern matching on trees and tree-like structures
• Binary jumbled string matching for highly run-length compressible texts
• Clustered Integer 3SUM via Additive Combinatorics
• Computing abelian complexity of binary uniform morphic words
• Efficient indexes for jumbled pattern matching with constant-sized alphabet
• Efficient randomized pattern-matching algorithms
• Fast algorithms for abelian periods in words and greatest common divisor queries
• How hard is it to find (honest) witnesses?
• Indexing permutations for binary strings
• Jewels of Stringology
• Long binary patterns are abelian 2-avoidable
• On hardness of jumbled indexing
• On shortest crucial words avoiding abelian powers
• On the asymptotic abelian complexity of morphic words
• Problems in between words and abelian words: \(k\)-abelian avoidability
• Sub-quadratic time and linear space data structures for permutation matching in binary strings
• Subquadratic-time algorithms for abelian stringology problems

Cited in

(8)

• String Periods in the Order-Preserving Model
• Fast algorithms for abelian periods in words and greatest common divisor queries
• A note on easy and efficient computation of full abelian periods of a word
• Finding patterns and periods in Cartesian tree matching
• Algorithms for computing abelian periods of words
• Fast computation of abelian runs
• Regular abelian periods and longest common abelian factors on run-length encoded strings
• 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)