Average complexity of exact and approximate multiple string matching

DOI10.1016/j.tcs.2004.03.058zbMath1070.68046OpenAlexW2011280787MaRDI QIDQ1885904

Gonzalo Navarro, Kimmo Fredriksson

Publication date: 12 November 2004

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

Full work available at URL: http://hdl.handle.net/10533/175115

zbMATH Keywords

Lower boundsMultipattern matchingString matching allowing differencesYao's bound

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

A weak approach to suffix automata simulation for exact and approximate string matching ⋮ On the bit-parallel simulation of the nondeterministic Aho-Corasick and suffix automata for a set of patterns ⋮ Average complexity of backward \(q\)-gram string matching algorithms ⋮ FLEXIBLE MUSIC RETRIEVAL IN SUBLINEAR TIME ⋮ Sequential and indexed two-dimensional combinatorial template matching allowing rotations

Cites Work

• Unnamed Item
• Speeding up two string-matching algorithms
• Fast practical multi-pattern matching
• An Improved Algorithm For Approximate String Matching
• Average-Optimal Multiple Approximate String Matching
• The Complexity of Pattern Matching for a Random String
• Efficient string matching
• Fast Pattern Matching in Strings
• Combinatorial Pattern Matching

This page was built for publication: Average complexity of exact and approximate multiple string matching