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