登入選單

返回Google圖書搜尋

Improving the Running Times for Some String-matching Problems

Sun WuUdi ManberE. W. Myers

出版	University of Arizona, Department of Computer Science, 1991
URL	http://books.google.com.hk/books?id=0RJFcgAACAAJ&hl=&source=gbs_api

註釋

Abstract: "We present new algorithms for three basic string- matching problems: 1) An algorithm for approximate string matching of a pattern of size m in a text of size n in worst-case time O(n + nm/log n), and average-case time O(n + nd/log n), where d is the number of allowed errors. 2) An algorithm to find the edit distance between two sequences of size n and m (n> m) in time O (n + nd/log n), where d is the edit distance. 3) An algorithm for approximate matching of a regular expression of size m in a text of size n in time O (n + nm/log [base d+2]n), where d is the number of allowed errors. The last algorithm is the first o(mn) algorithm for approximate matching to regular expressions."