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(m(n+e)) time and needs only O(n) extra space. This improves all previous results in both time and space complexity.