返回Google圖書搜尋

Efficient Comparison Based String Matching

出版	European Research Consortium for Informatics and Mathematics, 1992
URL	http://books.google.com.hk/books?id=teXIQwAACAAJ&hl=&source=gbs_api

註釋Abstract: "We study the exact number of symbol comparisons that are required to solve the string matching problem and present a family of efficient algorithms. Unlike previous string matching algorithms, the algorithms in this family do not 'forget' results of comparisons, what makes their analysis much simpler. In particular, we give a linear-time algorithm that finds all occurences of a pattern of length m in a text of length n in [formula] comparisons. The pattern preprocessing takes linear time and makes at most 2m comparisons. This algorithm establishes that, in general, searching for a long pattern is easier than searching for a short one