期刊
THEORETICAL COMPUTER SCIENCE
卷 237, 期 1-2, 页码 455-463出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/S0304-3975(99)00333-3
关键词
approximate structure matching; graph algorithms
The problem of approximate pattern matching on hypertext is defined and solved by Amir et al. in O(m(n log In + e)) time, where IH is the length of the pattern, II 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. (C) 2000 Elsevier Science B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据