finding sublist

[Shin-Cheng Mu]

On Mon, May 06, 2002 at 09:30:02AM +0200, Ketil Z. Malde wrote:
 > "Garner, Robin" <Robin.Garner@crsrehab.gov.au> writes:
 > > See Dijkstra's 'Discipline of Programming' for an o(M + N) algorithm - 
naive
 > > approches are o(MN) where M and N are the length of the list and 
substring
 > > respectively.
 > > Essentially the algorithm calculates a sort of autocorrelation table 
of the
 > > substring, showing where to resume the search after a failed match.
 > There's also the KMP (Knuth, Morris, Pratt) algorithm, which is
 > similar.  See Dan Gusfield: "Algorithms of strings, trees and
 > sequences" for lots of this stuff.

About 13 years back there was also a paper talking
about a formal derivation of such an algorithm in
a functional language, based on an important property
of fold and scan.

   R. S. Bird, J. Gibbons, and G. Jones.
   Formal derivation of a pattern matching algorithm.
   Science of Computer Programming, 12(2):93-104, July 1989.

sincerely,
Shin-Cheng Mu