Approximate periods of strings
From MaRDI portal
Publication:5958136
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)
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
