String cadences

DOI10.1016/J.TCS.2017.04.019zbMATH Open1380.68456arXiv1610.03337OpenAlexW4213248287MaRDI QIDQ1676299FDOQ1676299

Authors: Amihood Amir, Alberto Apostolico, Travis Gagie, Gad M. Landau 

Publication date: 6 November 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: We say a string has a cadence if a certain character is repeated at regular intervals, possibly with intervening occurrences of that character. We call the cadence anchored if the first interval must be the same length as the others. We give a sub-quadratic algorithm for determining whether a string has any cadence consisting of at least three occurrences of a character, and a nearly linear algorithm for finding all anchored cadences.

Full work available at URL: https://arxiv.org/abs/1610.03337

Recommendations

• Efficient detection of quasiperiodicities in strings
• Simple and flexible detection of contiguous repeats using a suffix tree
• Computing regularities in strings: a survey
• scientific article; zbMATH DE number 4078831
• Efficient construction of maximal and minimal representations of motifs of a string

zbMATH Keywords

pattern miningstring algorithmscadencesstring regularities

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Cites Work

• Introduction to algorithms
• Avoidable patterns in strings of symbols
• 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 algorithms for the periodic subgraphs mining problem
• Detecting approximate periodic patterns
• Finding longest approximate periodic patterns

Cited In (3)

• Skyrme Strings
• Cadences in grammar-compressed strings
• Bagatelle in C arranged for VDM SoLo

This page was built for publication: String cadences

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