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. For example, if you're matching the substring [1,2,3,4], and fail on the last comparison, you already know that there's no point in advancing one element and attempting another match - you can actually start again at the element that failed. When matching the string [1,2,1,3], you can resume at the current element of the main string, and the second element of the search string. How you would do this in a functional implementation is another question - Dijkstra's example is comparing two arrays, and there may be inefficiencies translating it to a list-based implementation. Cheers -----Original Message----- From: Serge D. Mechveliani [mailto:mechvel@botik.ru] Sent: Thursday, 2 May 2002 17:37 To: haskell@haskell.org Subject: finding sublist Thanks to people who helped me with the task
Import two space separated columns of integers from file.
Claus Reinke <claus.reinke@talk21.com> recommends to exploit `lines'. Indeed, it bocomes shorter now: main = readFile "data" >>= (putStr . show . twoIntLists) where twoIntLists str = case span (not . null) $ dropWhile null $ lines str of (lns, lns') -> (readInts lns, readInts lns') readInts = map (\ str -> read str :: Integer) . dropWhile null Another question: has the Haskell Standard library a function for such a usable task as finding of occurence of a segment in a list? Say findSegmentBy (...) [2,2,3] [0,0,2,2,1,2,2,3,1,2,3] --> ([0,0,2,2,1], [2,2,3,1,2,3]) I have heard, an efficient algorithm (for large lists) for this is not so simple. ----------------- Serge Mechveliani mechvel@botik.ru _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell