Which is the fastest pattern matching algorithm?

[tommazzo]

Hi!

I'm looking for a way to find the position of a certain pattern within a
string. On my search on the internet I've come accross various algorithms
such as Knuth-Morris-Pratt and Boyer-Moore (just to name two). But which is
the fastest?

Thanks already in advance!

[Patrice]

Run both in your real world conditions ;-)

Don't know but generally speaking you don't have a "faster" algorihtm. For
example one of these two could be quicker on small strings and the other
could be quicker on long strings, one could be quicker when there is
numerous close match etc etc.....

For a start I would use the regular expression that are readily available in
the .NET framework and that likely uses already something quite efficient.
Only if I can measure it doesn't fit my needs, I would then search if I
could do better. Try :

http://msdn.microsoft.com/library/de...ClassTopic.asp

(Also if the pattern is simple you could use the usual string functions...)

Patrice

--

"tommazzo" <to******@discussions.microsoft.com> a écrit dans le message de
news:80**********************************@microsof t.com...

Hi!

I'm looking for a way to find the position of a certain pattern within a
string. On my search on the internet I've come accross various algorithms
such as Knuth-Morris-Pratt and Boyer-Moore (just to name two). But which is the fastest?

Thanks already in advance!

[tommazzo]

Thanks a lot for your help! I'll conduct a few tests on both algorithms now.
However in the meantime I've already read that although the KMP algorithm has
a smaller number of worst-case character comparisons, the BM algorithm
usually turns up with the result after less comparisons and can thus be
considered more efficient.

"Patrice" wrote:

Run both in your real world conditions ;-)

Don't know but generally speaking you don't have a "faster" algorihtm. For
example one of these two could be quicker on small strings and the other
could be quicker on long strings, one could be quicker when there is
numerous close match etc etc.....

For a start I would use the regular expression that are readily available in
the .NET framework and that likely uses already something quite efficient.
Only if I can measure it doesn't fit my needs, I would then search if I
could do better. Try :

http://msdn.microsoft.com/library/de...ClassTopic.asp

(Also if the pattern is simple you could use the usual string functions...)

Patrice

--

"tommazzo" <to******@discussions.microsoft.com> a écrit dans le message de
news:80**********************************@microsof t.com...

Hi!

I'm looking for a way to find the position of a certain pattern within a
string. On my search on the internet I've come accross various algorithms
such as Knuth-Morris-Pratt and Boyer-Moore (just to name two). But which

is

the fastest?

Thanks already in advance!