1.7.4 Approximate String Matching
INPUT OUTPUT
Input Description:
A text string
t
and a pattern string
p
.
An edit cost bound
k
.
Problem:
Does there exist an alignment between
t
and
p
with edit
cost at most
k
, ie. can we transform part of
t
to
p
using at most
k
additions, deletions, and substitutions.
Implementations
agrep - Approximate General Regular Expression Pattern Matcher (C) (rating 10)
HT/DIG -- image compression codes (C) (rating 7)
Handbook of Algorithms and Data Structures (Pascal) (rating 2)
Related Problems
Longest Common Substring
String Matching
Go to the corresponding chapter in the book
About the Book
Send us Mail
Go to Main Page
This page last modified on Tue Jun 03, 1997
.