On Obtaining the Boyer-Moore String-Matching Algorithm by Partial Evaluation

Forfattere

  • Olivier Danvy
  • Henning Korsholm Rohde

DOI:

https://doi.org/10.7146/brics.v12i29.21896

Resumé

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.

Downloads

Publiceret

2005-09-11

Citation/Eksport

Danvy, O., & Rohde, H. K. (2005). On Obtaining the Boyer-Moore String-Matching Algorithm by Partial Evaluation. BRICS Report Series, 12(29). https://doi.org/10.7146/brics.v12i29.21896