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.