On the complexity of determining the period of a string

DOI10.1007/3-540-45123-4_34MaRDI QIDQ2723970zbMATH OpenFDO

Authors Artur Czumaj, Leszek Gąsieniec

Publication date 8 July 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-45123-4_34

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Nonnumerical algorithms (68W05)

Recommendations

• scientific article; zbMATH DE number 4078831
• scientific article; zbMATH DE number 4135398
• An O(n n) algorithm for computing all maximal quasiperiodicities in strings
• On the complexity of computing the order of repetition of a string
• Efficient detection of quasiperiodicities in strings

Cited in

(7)

• Approximating tree edit distance through string edit distance
• On the shortest common superstring of NGS reads
• Periodicity and cyclic shifts via linear sketches
• scientific article; zbMATH DE number 4078831 (Why is no real title available?)
• scientific article; zbMATH DE number 1092948 (Why is no real title available?)
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Linear-time computation of local periods

This page was built for publication: On the complexity of determining the period of a string

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