Average complexity of backward q-gram string matching algorithms
From MaRDI portal
Publication:436556
DOI10.1016/J.IPL.2012.02.010zbMATH Open1243.68336OpenAlexW1999933051MaRDI QIDQ436556FDOQ436556
Authors: Leena Salmela 
Publication date: 25 July 2012
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2012.02.010
Recommendations
- Average complexity of exact and approximate multiple string matching
- scientific article; zbMATH DE number 826062
- Approximate string-matching with \(q\)-grams and maximal matches
- Average-case linear-time similar substring searching by the \(q\)-gram distance
- Exact bounds on the complexity of sequential string matching algorithms
- Fast and linear-time string matching algorithms based on the distances of \(q\)-gram occurrences
- On the Exact Complexity of String Matching: Lower Bounds
- scientific article; zbMATH DE number 2149348
- Average-optimal string matching
- On the Exact Complexity of String Matching: Upper Bounds
Cites Work
- Speeding up two string-matching algorithms
- A fast string searching algorithm
- Fast Pattern Matching in Strings
- Fast and flexible string matching by combining bit-parallelism and suffix automata
- Average-optimal single and multiple approximate string matching
- The Complexity of Pattern Matching for a Random String
- Fast exact string matching algorithms
- Average complexity of exact and approximate multiple string matching
- Multipattern string matching with q -grams
- Approximate Boyer-Moore string matching for small alphabets
- Combinatorial Pattern Matching
- Improving practical exact string matching
This page was built for publication: Average complexity of backward \(q\)-gram string matching algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q436556)
