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

DOI10.1016/J.TCS.2014.02.022zbMATH Open1359.68337OpenAlexW2067704081MaRDI QIDQ2440164FDOQ2440164

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

• Title not available (Why is that?)
• Average complexity of backward \(q\)-gram string matching algorithms

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)