###
Improved Approximate Pattern Matching on Hypertext

####
Gonzalo Navarro

The problem of approximate pattern matching on hypertext is defined and
solved by Amir et al. in *O (m(n*log *m + e))* time, where
*m* is the length of the pattern, *n* is the total text size and
*e* is the total number of edges. Their space complexity is *O (mn)*.
We present a new algorithm which is *O (mk(n+e))* time and needs only
*O (n)* extra space, where *k is the number of allowed errors in
the pattern. If the graph is acyclic, our time complexity drops to
**O (m(n+e))**, improving Amir's work.
*