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(nlog 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.