Approximate periods of strings

DOI10.1016/S0304-3975(00)00365-0zbMath0983.68044MaRDI QIDQ5958136

W. F. Smyth, Costas S. Iliopoulos, Kun Soo Park, Jeong Seop Sim

Publication date: 3 March 2002

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

zbMATH Keywords

periodicitydistance functionapproximate periodsrepetitions

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items (13)

Multidimensional period recovery ⋮ A dynamic edit distance table ⋮ Can we recover the cover? ⋮ The approximate period problem for DNA alphabet. ⋮ String Covering: A Survey ⋮ Period recovery of strings over the Hamming and edit distances ⋮ ALGORITHMS FOR APPROXIMATE K-COVERING OF STRINGS ⋮ Approximate Periods with Levenshtein Distance ⋮ Generalized approximate regularities in strings ⋮ Approximate cover of strings ⋮ Quasi-Periodicity Under Mismatch Errors ⋮ Implementing approximate regularities ⋮ \(k\)-approximate quasiperiodicity under Hamming and edit distance

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A work-time optimal algorithm for computing all string covers
• Efficient detection of quasiperiodicities in strings
• Optimal superprimitivity testing for strings
• Pattern recognition in genetic sequences by mismatch density
• An optimal algorithm for computing the repetitions in a word
• The shortest common supersequence problem over binary alphabet is NP- complete
• Optimal off-line detection of repetitions in a string
• An on-line string superprimitivity test
• More on the complexity of common superstring and supersequence problems
• Testing string superprimitivity in parallel
• Two-dimensional prefix string matching and covering on square matrices
• Covering a string
• The subtree max gap problem with application to parallel string covering
• An O(n log n) algorithm for finding all repetitions in a string
• The Complexity of Some Problems on Subsequences and Supersequences
• Fast Pattern Matching in Strings
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• Incremental String Comparison
• Optimal parallel algorithms for periods, palindromes and squares
• An Optimal $O(\log \log N)$-Time Parallel Algorithm for Detecting all Squares in a String

This page was built for publication: Approximate periods of strings