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. > > However: it is very hard to beat the naive implementation > (i.e. something like '\p -> or . map isPrefixOf p . tails', untested) > in the expected case, at least in my experience. With an alphabet > > [..]
My suggestion was mainly to include this usable function (in its generic version) into Standard library. The possibility of clever algorithms for it is one more argument for such inlclusion. ----------------- Serge Mechveliani [EMAIL PROTECTED] _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
