The longest common extension problem revisited and applications to approximate string searching

DOI10.1016/j.jda.2010.08.004zbMath1213.68719OpenAlexW2002246332MaRDI QIDQ616995

Gonzalo Navarro, Lucian Ilie, Liviu Tinta

Publication date: 20 January 2011

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2010.08.004

zbMATH Keywords

Landau-Vishkin algorithmapproximate string searchlongest common extensionUkkonen's cutoff algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Algorithms on strings (68W32)

Related Items

Longest common extensions in trees, Time-Space Trade-Offs for Longest Common Extensions, Computing longest common extensions in partial words, On Maximal Unbordered Factors, Longest common extension, Fast and Simple Computations Using Prefix Tables Under Hamming and Edit Distance, Longest common substring with approximately \(k\) mismatches, Fast circular dictionary-matching algorithm, Time-space trade-offs for longest common extensions, Searching and Indexing Circular Patterns, A practical semi-external memory method for approximate pattern matching, Alignment-free sequence comparison using absent words, Range minimum queries in minimal space

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An \(O(ND)\) difference algorithm and its variations
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Engineering a lightweight suffix array construction algorithm
• Constructing suffix arrays in linear time
• Space efficient linear time construction of suffix arrays
• Suffix Arrays: A New Method for On-Line String Searches
• Fast Algorithms for Finding Nearest Common Ancestors
• An O(n log n) algorithm for finding all repetitions in a string
• Linear Time Suffix Array Construction Using D-Critical Substrings
• Finding approximate patterns in strings
• Algorithms for approximate string matching
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Recursive Star-Tree Parallel Data Structure
• Fast parallel and serial approximate string matching
• Algorithms on Strings, Trees and Sequences
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE