Period recovery of strings over the Hamming and edit distances

DOI10.1016/j.tcs.2017.10.026zbMath1386.68231OpenAlexW2767983873MaRDI QIDQ1698696

Mika Amit, Gad M. Landau, Dina Sokol, Amihood Amir

Publication date: 16 February 2018

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.10.026

zbMATH Keywords

Hamming distanceedit distanceapproximate periodicityperiod recovery

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items (2)

Multidimensional period recovery ⋮ Analysis of the Period Recovery Error Bound

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extracting powers and periods in a word from its runs structure
• How many double squares can a string contain?
• Efficient detection of quasiperiodicities in strings
• Optimal superprimitivity testing for strings
• Approximate matching of regular expressions
• An optimal algorithm for computing the repetitions in a word
• Identifying periodic occurrences of a template with applications to protein structure
• Finding approximate repetitions under Hamming distance.
• The approximate period problem for DNA alphabet.
• Covering problems for partial words and for indeterminate strings
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Speeding up the detection of evolutive tandem repeats
• Data structures and algorithms for the string statistics problem
• Speeding up the detection of tandem repeats over the edit distance
• Space efficient linear time construction of suffix arrays
• Cycle detection and correction
• Suffix Arrays: A New Method for On-Line String Searches
• Linear-Time Construction of Suffix Arrays
• Fast parallel and serial approximate string matching
• Error Detecting and Error Correcting Codes
• Locating All Maximal Approximate Runs in a String
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• Uniqueness Theorems for Periodic Functions
• Internal Pattern Matching Queries in a Text and Applications
• Computing the λ-Seeds of a String
• Algorithms on Strings
• On Burnside's Problem
• Computing the cover array in linear time
• Approximate periods of strings

This page was built for publication: Period recovery of strings over the Hamming and edit distances