On Mon, May 06, 2002 at 09:30:02AM +0200, Ketil Z. Malde wrote: > "Garner, Robin" <[EMAIL PROTECTED]> 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 _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
