Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Hello Perl monks,

I am looking for a perl program that implement the Knuth-Morris-Pratt algorithm to compare it to the standard Perl string matching expression in term of running time and memory spaces used. Does Perl used the same algorithm for its string pattern matching? Please provide some link to the code/
Thanks.

Replies are listed 'Best First'.
Re: Knuth-Morris-Pratt Vs. Perl
by CountZero (Bishop) on Nov 11, 2007 at 21:33 UTC
    I seem to have read somewhere that Perl uses the Boyer-Moore alorithm to do string searching rather than Knuth-Morris-Pratt.

    Update: A nice site comparing both algorithms.

    CountZero

    A program should be light and agile, its subroutines connected like a string of pearls. The spirit and intent of the program should be retained throughout. There should be neither too little or too much, neither needless loops nor useless variables, neither lack of structure nor overwhelming rigidity." - The Tao of Programming, 4.1 - Geoffrey James

[reply]
Re: Knuth-Morris-Pratt Vs. Perl
by CountZero (Bishop) on Nov 11, 2007 at 22:33 UTC
    In Mastering Algorithms with Perl you can find a Perl implementation of both algorithms. You can read it online here (you can subscribe to "Free Safari Trial" here)

    CountZero

    A program should be light and ag ile, its subroutines connected like a string of pearls. The spirit and intent of the program should be retained throughout. There should be neither too little or too much, neither needless loops nor useless variables, neither lack of structure nor overwhelming rigidity." - The Tao of Programming, 4.1 - Geoffrey James

[reply]
Re: Knuth-Morris-Pratt Vs. Perl
by Corion (Patriarch) on Nov 11, 2007 at 21:36 UTC

    Such a comparison is most likely useless, because the Perl string matching is written in C (and likely uses a Boyer-Moore search for longer strings), and your Perl implementation will either use (Perl) arrays of characters, which will be really slow or use Perls string search functions itself and thus likely be hampered by them.

    But as the sourcecode for Perl is easily downloadable, feel free to take a look at pp.c, the function fbm_instr.

    Usually, we only help people with their homework when they admit it's homework.

[reply]
[d/l]
[select]
[reply]
[d/l]
[select]

Back to Seekers of Perl Wisdom