Linear-Time Algorithm for Long LCF with k Mismatches

DOI10.4230/LIPIcs.CPM.2018.23zbMath1497.68598arXiv1802.06369OpenAlexW2964057579MaRDI QIDQ5140788

Tomasz Kociumaka, Maxime Crochemore, Panagiotis Charalampopoulos, Costas S. Iliopoulos, Solon P. Pissis, Tomasz Walen, Jakub Radoszewski, Wojciech Rytter

Publication date: 16 December 2020

Full work available at URL: https://arxiv.org/abs/1802.06369

zbMATH Keywords

Hamming distancedifference coverlongest common substringlongest common factorheavy-light decomposition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Algorithms on strings (68W32)

Related Items (6)

Efficient computation of sequence mappability ⋮ Longest common substring with approximately \(k\) mismatches ⋮ Near-optimal quantum algorithms for string problems ⋮ Faster algorithms for 1-mappability of a sequence ⋮ Longest property-preserved common factor: a new string-processing framework ⋮ Longest common substring made fully dynamic

Uses Software

• ALFRED

Cites Work

• Unnamed Item
• Computing the longest common substring with one mismatch
• Which problems have strongly exponential complexity?
• A note on the longest common substring with \(k\)-mismatches problem
• Longest common substrings with \(k\) mismatches
• Longest repeats with a block of \(k\) don't cares
• Sublinear Space Algorithms for the Longest Common Substring Problem
• Applications of Path Compression on Balanced Trees
• Fast Lightweight Suffix Array Construction and Checking
• Dictionary matching and indexing with errors and don't cares
• A Fast Merging Algorithm
• Algorithms on Strings, Trees and Sequences
• Sorting jordan sequences in linear time using level-linked search trees
• Time-Space Trade-Offs for the Longest Common Substring Problem
• Longest Common Prefixes with k-Mismatches and Applications
• More Applications of the Polynomial Method to Algorithm Design
• Longest Common Substring with Approximately k Mismatches
• On the complexity of \(k\)-SAT

This page was built for publication: Linear-Time Algorithm for Long LCF with k Mismatches