𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Analysis of two-dimensional approximate pattern matching algorithms

✍ Scribed by Park Kunsoo

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
717 KB
Volume
201
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

We present a new and more rigorous analysis of the two algorithms for two-dimensional approximate pattern matching due to KtikkEnen and Ukkonen. We also present modifications of these algorithms that use less space while keeping the same expected time.

πŸ“œ SIMILAR VOLUMES

A Comparison of Approximate String Match
A Comparison of Approximate String Matching Algorithms
✍ PETTERI JOKINEN; JORMA TARHIO; ESKO UKKONEN πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 972 KB

Experimental comparisons of the running time of approximate string matching algorithms for the k differences problem are presented. Given a pattern string, a text string, and an integer k, the task is to find all approximate occurrences of the pattern in the text with at most k differences (insertio