Average complexity of backward \(q\)-gram string matching algorithms

DOI10.1016/j.ipl.2012.02.010zbMath1243.68336OpenAlexW1999933051MaRDI QIDQ436556

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

zbMATH Keywords

analysis of algorithmsstring matchingaverage case complexity

Mathematics Subject Classification ID

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

Cites Work

• Fast exact string matching algorithms
• Improving practical exact string matching
• Speeding up two string-matching algorithms
• Average complexity of exact and approximate multiple string matching
• Approximate Boyer-Moore string matching for small alphabets
• A fast string searching algorithm
• Multipattern string matching with q -grams
• The Complexity of Pattern Matching for a Random String
• 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
• Combinatorial Pattern Matching