String cadences

DOI10.1016/J.TCS.2017.04.019MaRDI QIDQ1676299zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

pattern miningstring algorithmscadencesstring regularities

Mathematics Subject Classification ID

Algorithms on strings (68W32)

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.

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

Cites work

• scientific article; zbMATH DE number 3118808 (Why is no real title available?)
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 1024080 (Why is no real title available?)
• scientific article; zbMATH DE number 799788 (Why is no real title available?)
• scientific article; zbMATH DE number 918133 (Why is no real title available?)
• scientific article; zbMATH DE number 3062467 (Why is no real title available?)
• Avoidable patterns in strings of symbols
• Detecting approximate periodic patterns
• Efficient algorithms for the periodic subgraphs mining problem
• Finding longest approximate periodic patterns
• Introduction to algorithms

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)