Average-case linear-time similar substring searching by the q-gram distance

DOI10.1016/J.TCS.2014.02.022MaRDI QIDQ2440164zbMATH OpenOpenAlexFDO

Authors Hiroyuki Hanada, Mineichi Kudo, Atsuyoshi Nakamura

Publication date 27 March 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.02.022

zbMATH Keywords

string searchingapproximate string matching\(q\)-gram distance

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 826062
• Computing the Threshold for q-Gram Filters
• Approximate string-matching with q-grams and maximal matches
• scientific article; zbMATH DE number 2149348
• scientific article; zbMATH DE number 1342989

Cites work

• scientific article; zbMATH DE number 493074 (Why is no real title available?)
• Algorithms on Strings, Trees and Sequences
• Approximate string-matching with q-grams and maximal matches
• Fast Pattern Matching in Strings
• Fast parallel and serial approximate string matching
• Finding approximate patterns in strings
• Introduction to algorithms
• Simple and efficient string matching with k mismatches
• Sublinear approximate string matching and biological applications
• The theory and computation of evolutionary distances: Pattern recognition
• Vector representations for efficient comparison and search for similar strings

Cited in

(2)

• scientific article; zbMATH DE number 826062 (Why is no real title available?)
• Average complexity of backward \(q\)-gram string matching algorithms

Describes a project that uses

Uses Software

• BWA

This page was built for publication: Average-case linear-time similar substring searching by the \(q\)-gram distance

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