[Haskell-cafe] Text search

Gracjan Polak gracjan at acchsh.com
Mon May 16 08:00:33 EDT 2005


Ketil Malde wrote:
 > Gracjan Polak <gracjan at acchsh.com> writes:
 >
 >
 >>find (isSuffixOf "needle") (inits "haystack")
 >
 >
 > Hmm...
 >
 > While the result isn't exactly the same, I suspect
 > using isPrefixOf and tails would be more efficient.
 >

I need the data before and including my needle. Like this:

( ... needle ) ignored

Or at least count of the first part. Or, best, pair of: 
(beforeandincluding,after).

String is rather long (potentially infinite), so using reverse and tail 
could be a problem :)

 >
 >>This one is beautiful, but not very practical.
 >
 >
 > Unless you have very repetitive data and/or tiny alphabet, it is
 > actually quite efficient, as the expected length of prefixes that need
 > to be checked before a mismatch can be determined is small.
 >
 > At least, I was unable to beat it with my (feeble attempts at) BM or
 > KMP implementations.
 >
 > -kzm



More information about the Haskell-Cafe mailing list