๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Approximate regular expression matching with multi-strings

โœ Scribed by Belazzougui, Djamal; Raffinot, Mathieu

Book ID
122800777
Publisher
Elsevier Science
Year
2013
Tongue
English
Weight
285 KB
Volume
18
Category
Article
ISSN
1570-8667

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

A Subquadratic Algorithm for Approximate
A Subquadratic Algorithm for Approximate Regular Expression Matching
โœ S. Wu; U. Manber; E. Myers ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 673 KB

The main result of this paper is an algorithm for approximate matching of a regular expression of size \(m\) in a text of size \(n\) in time \(O\left(n m / \log _{d+2} n\right)\), where \(d\) is the number of allowed errors. This algorithm is the first \(o(m n)\) algorithm for approximate matching t