> Hi again,
>
[quoted text clipped - 6 lines]
> What's the best/fastest algorithm for a usual buffer size of
> 1500bytes or so? Is there any source code available for this?
1500 bytes is actually a pretty small buffer by today's standards.
Depending on the buffer contents, the length of the pattern, and the number
and length of "false starts" (prefixes of the pattern that appear in the
buffer), any one of several different algorithms might be the best/fastest.
The first-order solution is to use the strstr() library function, but that
will only work if your buffer doesn't contain embedded nulls.
If you really do need a high-end algorithm, do some searching for the
Boyer-Moore algorithm or the Knuth-Morris-Pratt algorithm. Both are well
described in online resources and source code implementations are available
if you do some hunting. For the size of your buffer, it's entirely possible
that a brute-force search will be as fast as these fancy algorithms, so you
should code up the brute-force solution (or use strstr) for comparison and
keep whichever gives the best performance on your particular data.
-cd
Carl Daniel [VC++ MVP] - 12 Sep 2004 17:13 GMT
>> Hi again,
>>
[quoted text clipped - 23 lines]
> solution (or use strstr) for comparison and keep whichever gives the
> best performance on your particular data.
And I forgot to mention: there's always std::find with a suitable
predicate. That's likely to be a brute-force implementation, but it's
always possible that std::find might have an optimized version that uses
Boyer-Moore or another high-end searching algorithm.
-cd