Longest Common Substring with Approximately k Mismatches

DOI10.4230/LIPIcs.CPM.2016.21zbMath1380.68482OpenAlexW2615245491MaRDI QIDQ5369556

Tatiana Starikovskaya

Publication date: 17 October 2017

Full work available at URL: https://hal.science/hal-03942914

zbMATH Keywords

sketchinglongest common substringrandomised algorithmslocality-sensitive hashingstring similarity measures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Randomized algorithms (68W20) Algorithms on strings (68W32)

Related Items (8)

A new distributed alignment-free approach to compare whole proteomes ⋮ Longest common substring with approximately \(k\) mismatches ⋮ Near-optimal quantum algorithms for string problems ⋮ Dynamic and internal longest common substring ⋮ Longest Common Factor After One Edit Operation ⋮ Longest common substring made fully dynamic ⋮ Locally Maximal Common Factors as a Tool for Efficient Dynamic String Algorithms. ⋮ Linear-Time Algorithm for Long LCF with k Mismatches

This page was built for publication: Longest Common Substring with Approximately k Mismatches