Locating maximal approximate runs in a string

DOI10.1016/j.tcs.2017.07.021zbMath1390.68782OpenAlexW2742555398MaRDI QIDQ2410363

Maxime Crochemore, Gad M. Landau, Mika Amit, Dina Sokol

Publication date: 17 October 2017

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

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

zbMATH Keywords

Hamming distancepattern matchingrepetitionstandem repeatsrunsalgorithms on strings

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• New simple efficient algorithms computing powers and runs in strings
• Replacing suffix trees with enhanced suffix arrays
• Lempel-Ziv factorization using less time \& space
• Computing longest previous factor in linear time and applications
• An optimal algorithm for computing the repetitions in a word
• Optimal off-line detection of repetitions in a string
• A characterization of the squares in a Fibonacci string
• Finding approximate repetitions under Hamming distance.
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Detecting leftmost maximal periodicities
• Speeding up the detection of evolutive tandem repeats
• Space efficient linear time construction of suffix arrays
• An O(n log n) algorithm for finding all repetitions in a string
• Linear-Time Construction of Suffix Arrays
• Fast parallel and serial approximate string matching
• Algorithms on Strings
• On Context-Free Languages

This page was built for publication: Locating maximal approximate runs in a string