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 extra space complexity is O(mn). We present a new algorithm which is O(m(n + e)) time and needs only O(n) extra space. This improves all previous results in both time and space complexity.
['Gonzalo Navarro']
Improved approximate pattern matching on hypertext