In article <11**********************@e3g2000cwe.googlegroups. com>,

laura <la*************@gmail.comwrote:

>I'm looking for the algorithm which does the lowest number of

comparison for the string matching problem (in the worst case).

That's an algorithms question, not a C specific question, so you

are advised to check with a newsgroup that deals with algorithms.

>I know that the complexity is liniar in the length of the strings, but

I'm interested in finding the actual number of comparisons.

You haven't defined *which* "string matching problem" you are

dealing with. It is also rather odd that you are concentrating

on the worst case to the exclusion of the average case.

>The lowest number (theoretical) is m-n+1, but as far as I know no

algorithm has achived this limit.

That's not the theoretical limit when you take into account locale

problems and case sensitivity...

--

"law -- it's a commodity"

-- Andrew Ryan (The Globe and Mail, 2005/11/26)