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

DOI10.1016/J.JDA.2010.08.004zbMATH Open1213.68719OpenAlexW2002246332MaRDI QIDQ616995FDOQ616995

Authors: Lucian Ilie, Gonzalo Navarro, 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

Recommendations

• Longest common extensions via fingerprinting
• Time-Space Trade-Offs for Longest Common Extensions
• Longest common extensions in sublinear space
• Time-space trade-offs for longest common extensions
• Longest common extensions in trees

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (21)

• Searching and indexing circular patterns
• Developments in Language Theory
• Computing longest common extensions in partial words
• On maximal unbordered factors
• Fast and simple computations using prefix tables under Hamming and edit distance
• Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
• Tight lower bounds for the longest common extension problem
• Time-Space Trade-Offs for Longest Common Extensions
• Computing the Longest Unbordered Substring
• Longest common extensions in trees
• Locally maximal common factors as a tool for efficient dynamic string algorithms
• Longest common substring with approximately \(k\) mismatches
• Range minimum queries in minimal space
• Longest property-preserved common factor: a new string-processing framework
• Faster longest common extension queries in strings over general alphabets
• Fast circular dictionary-matching algorithm
• Longest common extension
• Longest common extensions via fingerprinting
• Time-space trade-offs for longest common extensions
• Alignment-free sequence comparison using absent words
• A practical semi-external memory method for approximate pattern matching

This page was built for publication: The longest common extension problem revisited and applications to approximate string searching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q616995)