findSubstring deprecated

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

findSubstring deprecated

Rafael Gustavo da Cunha Pereira Pinto-2
Two quick questions:

1) Is there any replacement for the (now deprecated) findSubstring function
on ByteString.Char8?
2) Does it work with ByteString.Lazy.Char8?

Best Regards,


Rafael Gustavo da Cunha Pereira Pinto
Electronic Engineer, MSc.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20080826/9e85c7a5/attachment.htm
Reply | Threaded
Open this post in threaded view
|

findSubstring deprecated

Daniel Fischer-4
Am Dienstag, 26. August 2008 17:43 schrieb Rafael Gustavo da Cunha Pereira
Pinto:

> Two quick questions:
>
> 1) Is there any replacement for the (now deprecated) findSubstring function
> on ByteString.Char8?
> 2) Does it work with ByteString.Lazy.Char8?
>
> Best Regards,
>
>
> Rafael Gustavo da Cunha Pereira Pinto
> Electronic Engineer, MSc.

Use the stringsearch package:
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stringsearch

That has pretty fast stringsearch functions (usually, Boyer-Moore is faster
than Knuth-Morris-Pratt) for strict and lazy ByteStrings.
I'm not sure if it works on ByteString(.Lazy).Char8, too, or only on Word8
ByteStrings, but it would be trivial to adapt, just change the import.

There's one thing to be aware of, however, if there are overlapping occurences
of the searched-for string, KMP reports only the first of their indices, BM
all.

Maybe we should complete it and also add search&replace functions?

Cheers,
Daniel
Reply | Threaded
Open this post in threaded view
|

findSubstring deprecated

Rafael Gustavo da Cunha Pereira Pinto
Thanks!

Either KMP or BM are good for me as I will probably do a (take 1 $ matchSL
pat list)  on it.

KMP is O(n+m), right?

Regards,
Rafael

On Tue, Aug 26, 2008 at 18:43, Daniel Fischer <[hidden email]>wrote:

> Am Dienstag, 26. August 2008 17:43 schrieb Rafael Gustavo da Cunha Pereira
> Pinto:
> > Two quick questions:
> >
> > 1) Is there any replacement for the (now deprecated) findSubstring
> function
> > on ByteString.Char8?
> > 2) Does it work with ByteString.Lazy.Char8?
> >
> > Best Regards,
> >
> >
> > Rafael Gustavo da Cunha Pereira Pinto
> > Electronic Engineer, MSc.
>
> Use the stringsearch package:
> http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stringsearch
>
> That has pretty fast stringsearch functions (usually, Boyer-Moore is faster
> than Knuth-Morris-Pratt) for strict and lazy ByteStrings.
> I'm not sure if it works on ByteString(.Lazy).Char8, too, or only on Word8
> ByteStrings, but it would be trivial to adapt, just change the import.
>
> There's one thing to be aware of, however, if there are overlapping
> occurences
> of the searched-for string, KMP reports only the first of their indices, BM
> all.
>
> Maybe we should complete it and also add search&replace functions?
>
> Cheers,
> Daniel
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/beginners
>



--
Rafael Gustavo da Cunha Pereira Pinto
Electronic Engineer, MSc.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20080827/bead38d6/attachment.htm
Reply | Threaded
Open this post in threaded view
|

findSubstring deprecated

Daniel Fischer-4
Am Mittwoch, 27. August 2008 13:19 schrieb Rafael Gustavo da Cunha Pereira
Pinto:
> Thanks!
>
> Either KMP or BM are good for me as I will probably do a (take 1 $ matchSL
> pat list)  on it.
>
> KMP is O(n+m), right?

Yes, and it doesn't have bad constant factors, but take into account the last
paragraphs of
http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm
to decide which one to use.
>
> Regards,
> Rafael
Cheers,
Daniel