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