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

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

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/

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

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?)
• 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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Algorithms for computing abelian periods of words
• Abelian squares are avoidable on 4 letters
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• How hard is it to find (honest) witnesses?
• 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 (8)

• Regular Abelian Periods and Longest Common Abelian Factors on Run-Length Encoded Strings
• 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
• 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)