Approximate periodicity

DOI10.1016/j.ic.2015.02.004zbMath1314.68416OpenAlexW2911636427MaRDI QIDQ2343134

Avivit Levy, Estrella Eisenberg, Amihood Amir

Publication date: 4 May 2015

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2015.02.004

zbMATH Keywords

Hamming distanceapproximate string matchingstring periodicityapproximate periodicityswap distance

Mathematics Subject Classification ID

Combinatorics on words (68R15) Approximation algorithms (68W25) Algorithms on strings (68W32)

Related Items

Multidimensional period recovery

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A space efficient algorithm for finding the best nonoverlapping alignment score
• Periodicity and repetitions in parameterized strings
• Efficient string matching with k mismatches
• An optimal algorithm for computing the repetitions in a word
• Optimal parallel two dimensional text searching on a CREW PRAM
• Fast algorithms for approximately counting mismatches
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Approximate swapped matching.
• Cycle detection and correction
• Approximate Periodicity
• Closest Periodic Vectors in L p Spaces
• Fast Algorithms for Finding Nearest Common Ancestors
• An O(n log n) algorithm for finding all repetitions in a string
• A New Algorithm for Efficient Pattern Matching with Swaps
• Optimal parallel algorithms for string matching
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• Two-Dimensional Periodicity in Rectangular Arrays
• Alphabet-Independent Two-Dimensional Witness Computation
• An Algorithm for Locating Nonoverlapping Regions of Maximum Alignment Score
• A New Model to Solve the Swap Matching Problem and Efficient Algorithms for Short Patterns
• Algorithms – ESA 2004