A linear-time algorithm for the 1-mismatch problem

DOI10.1007/3-540-63307-3_53MaRDI QIDQ5096932zbMATH OpenOpenAlexFDO

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

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 charactercenter sequenceextra spacelocus control regionprocedure center

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1445379
• Mismatch sampling
• Faster algorithms for string matching with k mismatches
• Fast algorithms for approximately counting mismatches
• Linear-time algorithm for long LCF with k mismatches

Cites work

• Data structures and algorithms for approximate string matching

Cited in

(9)

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

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

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