finding sublist

[Serge D. Mechveliani]

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.
> 
> 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
mechvel@botik.ru