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:[EMAIL PROTECTED]]
Sent: Thursday, 2 May 2002 17:37
To: [EMAIL PROTECTED]
Subject: finding sublist
Thanks to people who helped me with the task
>> Import two space separated columns of integers from file.
Claus Reinke <[EMAIL PROTECTED]> 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
[EMAIL PROTECTED]
_______________________________________________
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
