Re: [Ocaml-lib-devel] ExtString module updated

[Hideo B. <ba...@im...>]

Hello,

A minor comment.

At Thu, 22 May 2003 10:51:25 -0500 (CDT),
Brian Hurt wrote:
> Sanity check this code, if you will:
>
> let kmp p =
(snip)

The algorithm looks to me like "Morris-Pratt" (MP),
and not "Knuth-Morris-Pratt" (KMP). KMP tries to exploit
a bit more information in the pattern in the preprocessing
stage to reduce redundant comparisons during the matching.

This may be a different issue but, I have heard (and read)
that Boyer-Moore style algorithms are much faster in practice,
often having a sub linear runtime (but I have never done any
benchmarks myself).

There are so many zillions of different algorithms!
e.g.:
  http://www-igm.univ-mlv.fr/~lecroq/string/index.html

but I guess almost everyone will only need one reasonable
implementation. Just something to think about.

--
Hideo Bannai <ba...@im...>
Human Genome Center, Institute of Medical Science, University of Tokyo
4-6-1 Shirokanedai, Minato-ku, Tokyo 108-8639, Japan.
Phone: +81-3-5449-5615 Fax  : +81-3-5449-5442