Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Calculational developments of functional programs have been likened to conjuring tricks: enjoyable to watch but often a mystery as to how they are done. This pearl explains the trick. The aim is to give new calculations of two famous algorithms in string matching, the Knuth-Morris-Pratt algorithm and the Boyer-Moore algorithm. The string matching problem is formulated polymorphically, so the only available property of elements of the alphabet is an equality test.

REFERENCES

• 1: Ager, M S, Danvy, O, Rohde, H K. Fast partial evaluation of pattern matching in strings. BRICS Report Series, RS-03-11, University of Aarhus, Denmark, 2003.
• 2: R. S. Bird, Improving programs by the introduction of recursion, Communications of the ACM, v.20 n.11, p.856-863, Nov. 1977 [doi>10.1145/359863.359889]
• 3: Bird, R S. Introduction to Functional Programming using Haskell Prentic Hall Europe, 1988.
• 4: R. S. Bird , J. Gibbons , G. Jones, Formal derivation of a pattern matching algorithm, Science of Computer Programming, v.12 n.2, p.93-104, July 1989 [doi>10.1016/0167-6423(89)90036-1]
• 5: Crochemore, M, and Rytter, W. Jewels of Stringology. World Scientific, Hong Kong, 2002.
• 6: Danvy, O and Rohde, H K. On obtaining the Boyer-Moore string-matching algorithm by partial evaluation. BRICS Research Report RS-05-14, University of Aarhus, Denmark, 2005.
• 7: Zvi Galil, On improving the worst case running time of the Boyer-Moore string matching algorithm, Communications of the ACM, v.22 n.9, p.505-508, Sept. 1979 [doi>10.1145/359146.359148]
• 8: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 9: Thierry Lecroq, Experimental results on string matching algorithms, Software—Practice & Experience, v.25 n.7, p.727-765, July 1995 [doi>10.1002/spe.4380250703]

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming

General Terms:
Algorithms, Verification

Keywords:
boyer-moore, functional programming, knuth-morris-pratt, program calculation, string matching