Version française
Home     About     Download     Resources     Contact us    
Browse thread
Knuth-Morris-Pratt
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Alain Frisch <alain@f...>
Subject: Re: [Caml-list] Knuth-Morris-Pratt
Christopher L Conway wrote:
> Hmm. My KMP implementation turned out to be a real bottleneck in my
> ICFP code; I suspected I should have chosen Boyer-Moore (not knowing
> anything about the constant factors of each, just stabbing in the
> dark)... Maybe it was the average-case O(log n) "get" in my "rope"
> implementation...

Boyer-Moore is more useful with a large alphabet. With only 4
characters, I don't think it would have helped you a lot for the contest
(I might be wrong).

-- Alain