Faster algorithms for longest common substring
From MaRDI portal
Cites work
- A Fast Merging Algorithm
- A linear size index for approximate pattern matching
- A linear-time algorithm for a special case of disjoint set union
- A note on the longest common substring with k-mismatches problem
- Accelerating Boyer Moore Searches on Binary Texts
- Algorithmic Framework for Approximate Matching Under Bounded Edits with Applications to Sequence Analysis
- Algorithms on Strings
- Alphabet-independent compressed text indexing
- Approximate pattern matching with \(k\)-mismatches in packed text
- Approximate string matching using compressed suffix arrays
- Approximate String Matching: A Simpler Faster Algorithm
- Approximating Longest Common Substring with k mismatches: Theory and Practice
- Circular pattern matching with \(k\) mismatches
- Compressed indexes for approximate string matching
- Computing the longest common substring with one mismatch
- Constant-time word-size string matching
- Deterministic indexing for packed strings
- Deterministic sorting in O(nloglogn) time and linear space
- Dictionary matching and indexing with errors and don't cares
- Dynamic and internal longest common substring
- Dynamic longest common substring in polylogarithmic time
- Dynamic ordered sets with exponential search trees
- Efficient algorithms to compute compressed longest common substrings and compressed palindromes
- Efficient computation of sequence mappability
- Efficient fully-compressed sequence representations
- Examining Computational Geometry, Van Emde Boas Trees, and Hashing from the Perspective of the Fusion Tree
- Fast compressed self-indexes with deterministic linear-time construction
- Fast construction of wavelet trees
- Fast index for approximate string matching
- Fast lightweight suffix array construction and checking
- Fast searching in packed strings
- Fast Searching in Packed Strings
- Faster approximate pattern matching: a unified approach
- Few matches or almost periodicity: faster pattern matching with mismatches in compressed texts
- Finding maximal repetitions in a word in linear time
- scientific article; zbMATH DE number 1615296 (Why is no real title available?)
- scientific article; zbMATH DE number 2079421 (Why is no real title available?)
- scientific article; zbMATH DE number 1512678 (Why is no real title available?)
- scientific article; zbMATH DE number 6297698 (Why is no real title available?)
- scientific article; zbMATH DE number 7651096 (Why is no real title available?)
- scientific article; zbMATH DE number 7651115 (Why is no real title available?)
- scientific article; zbMATH DE number 7740885 (Why is no real title available?)
- Improved space-time tradeoffs for approximate full-text indexing with one edit error
- Linear time runs over general ordered alphabets
- Linear-time algorithm for long LCF with k mismatches
- Locally maximal common factors as a tool for efficient dynamic string algorithms
- Log-logarithmic worst-case range queries are possible in space theta(N)
- Longest common factor after one edit operation
- Longest common prefixes with k-errors and applications
- Longest common substring with approximately \(k\) mismatches
- Longest common substrings with k mismatches
- Longest palindromic substring in sublinear time
- Longest repeats with a block of \(k\) don't cares
- Lower bounds for text indexing with mismatches and differences
- Lyndon arrays in sublinear time
- More applications of the polynomial method to algorithm design
- Near-optimal quantum algorithms for string problems
- On the complexity of k-SAT
- Optimal lower and upper bounds for representing sequences
- Optimal near-linear space heaviest induced ancestors
- Optimal suffix tree construction with large alphabets
- Pattern Matching with Swaps for Short Patterns in Linear Time
- Preserving order in a forest in less than logarithmic time and linear space
- Property Suffix Array with Applications in Indexing Weighted Sequences
- Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
- Quantum speed-ups for string synchronizing sets, longest common substring, and k-mismatch matching
- Quorums from difference covers
- Reducing structural changes in van Emde Boas' data structure to the lower bound for the dynamic predecessor problem
- Shift-or string matching with super-alphabets
- Space-efficient construction of compressed indexes in deterministic linear time
- String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure
- Sublinear space algorithms for the longest common substring problem
- Sublinear time Lempel-Ziv (LZ77) factorization
- Suffix Arrays: A New Method for On-Line String Searches
- The ``runs theorem
- The heaviest induced ancestors problem: better data structures and applications
- Time-optimal top-k document retrieval
- Time-space trade-offs for the longest common substring problem
- Towards optimal packed string matching
- Uniqueness Theorems for Periodic Functions
- Wavelet trees meet suffix trees
- Which problems have strongly exponential complexity?
- Worst case efficient single and multiple string matching in the RAM model
This page was built for publication: Faster algorithms for longest common substring
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7299204)
