the lowest number of comparisons in string matching

[laura]

Hi,

I'm looking for the algorithm which does the lowest number of
comparison for the string matching problem (in the worst case).

I know that the complexity is liniar in the length of the strings, but
I'm interested in finding the actual number of comparisons.

The lowest number (theoretical) is m-n+1, but as far as I know no
algorithm has achived this limit.

(where m is the lenght of the text and n is the length of the pattern).

Thanks,
Laura

[CBFalconer]

laura wrote:

>
I'm looking for the algorithm which does the lowest number of
comparison for the string matching problem (in the worst case).

I know that the complexity is liniar in the length of the strings,
but I'm interested in finding the actual number of comparisons.

The lowest number (theoretical) is m-n+1, but as far as I know no
algorithm has achived this limit.

(where m is the lenght of the text and n is the length of the
pattern).

This is off-topic here. Try comp.programming. Cross posted and
followups set.

Search for Boyer-Moore and Knuth-Morris-Pratt algorithms.
Sedgewicks "Algorithms" covers it nicely. KMP is nice in that it
avoids backtracking and works with streams.

--
Some informative links:
news:news.announce.newusers
http://www.geocities.com/nnqweb/
http://www.catb.org/~esr/faqs/smart-questions.html
http://www.caliburn.nl/topposting.html
http://www.netmeister.org/news/learn2quote.html

--
Posted via a free Usenet account from http://www.teranews.com

[Walter Roberson]

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)