A linear-time algorithm for the 1-mismatch problem

DOI10.1007/3-540-63307-3_53zbMath1497.68606OpenAlexW1559357409MaRDI QIDQ5096932

Ross C. Hardison, Webb Miller, Nikola Stojanović, Deborah Gumucio, Piotr Berman

Publication date: 19 August 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-63307-3_53

zbMATH Keywords

center sequenceextra spacecenter characterlocus control regionprocedure center

Mathematics Subject Classification ID

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

Related Items (8)

Configurations and minority in the string consensus problem ⋮ A three-string approach to the closest string problem ⋮ Combinatorial \(n\)-fold integer programming and applications ⋮ Parameterized complexity analysis for the closest string with wildcards problem ⋮ Efficient algorithms for consensus string problems minimizing both distance sum and radius ⋮ Closest substring problems for regular languages ⋮ Consensus string problem for multiple regular languages ⋮ Randomized fixed-parameter algorithms for the closest string problem

Cites Work

• Data structures and algorithms for approximate string matching

This page was built for publication: A linear-time algorithm for the 1-mismatch problem