On-line approximate string matching with bounded errors

DOI10.1016/j.tcs.2011.08.005zbMath1233.68232OpenAlexW2122990924MaRDI QIDQ653329

Claudio Telha, Gonzalo Navarro, Marcos A. Kiwi

Publication date: 9 January 2012

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

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

zbMATH Keywords

string matching algorithmsstring matching problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Cites Work

• Unnamed Item
• Approximate string-matching with \(q\)-grams and maximal matches
• Self-testing/correcting with applications to numerical problems
• Sublinear approximate string matching and biological applications
• Handbook of randomized computing. Vols. 1, 2
• On-Line Approximate String Matching with Bounded Errors
• Approximate Boyer–Moore String Matching
• Large deviations for sums of partly dependent random variables
• Average-optimal single and multiple approximate string matching
• Concentration of Measure for the Analysis of Randomized Algorithms