文章基本信息

标题：On Obtaining the Boyer-Moore String-Matching Algorithm by Partial Evaluation
本地全文：下载
作者：Olivier Danvy ; Henning Korsholm Rohde
期刊名称：BRICS Report Series
印刷版ISSN：0909-0878
出版年度：2005
卷号：12
期号：14
出版社：Aarhus University
摘要：We present the first derivation of the search phase of the Boyer-Moore string-matching algorithm by partial evaluation of an inefficient string matcher. The derivation hinges on identifying the `bad-character-shift' heuristic as a binding-time improvement, bounded static variation. An inefficient string matcher incorporating this binding-time improvement specializes into the search phase of the Horspool algorithm, which is a simplified variant of the Boyer-Moore algorithm. Combining the bad-character-shift binding-time improvement with our previous results yields a new binding-time-improved string matcher that specializes into the search phase of the Boyer-Moore algorithm.