Average complexity of backward \(q\)-gram string matching algorithms
type: Item
instance of: scholarly article
title: Average complexity of backward \(q\)-gram string matching algorithms
zbMATH Open document ID: 1243.68336
author: Leena Salmela
published in: Information Processing Letters
publication date: 2012-07-25T00:00:00Z
Mathematics Subject Classification ID: 68W32
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 6059682
zbMATH Keywords: analysis of algorithms
zbMATH Keywords: string matching
zbMATH Keywords: average case complexity
MaRDI profile type: Publication
full work available at URL: j.ipl.2012.02.010
OpenAlex ID: W1999933051
cites work: Average-optimal single and multiple approximate string matching
cites work: Combinatorial Pattern Matching
cites work: Multipattern string matching with q -grams
cites work: Approximate Boyer-Moore string matching for small alphabets
cites work: Improving practical exact string matching
cites work: Fast exact string matching algorithms
cites work: Speeding up two string-matching algorithms
cites work: A fast string searching algorithm
cites work: Fast Pattern Matching in Strings
cites work: The Complexity of Pattern Matching for a Random String
cites work: Fast and flexible string matching by combining bit-parallelism and suffix automata
cites work: Average complexity of exact and approximate multiple string matching
DOI: 10.1016/J.IPL.2012.02.010
Recommended article: Average complexity of exact and approximate multiple string matching
Recommended article: Q4858448
Recommended article: Approximate string-matching with \(q\)-grams and maximal matches
Recommended article: Average-case linear-time similar substring searching by the \(q\)-gram distance
Recommended article: Exact bounds on the complexity of sequential string matching algorithms
Recommended article: Fast and linear-time string matching algorithms based on the distances of \(q\)-gram occurrences
Recommended article: On the Exact Complexity of String Matching: Lower Bounds
Recommended article: Q4661875
Recommended article: Average-optimal string matching
Recommended article: On the Exact Complexity of String Matching: Upper Bounds
description: scientific article; zbMATH DE number 6059682