the lowest number of comparisons in string matching

L

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
 
C

CBFalconer

laura said:
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:
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
 
W

Walter Roberson

laura said:
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...
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,731
Messages
2,569,432
Members
44,832
Latest member
GlennSmall

Latest Threads

Top