By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
435,435 Members | 2,939 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,435 IT Pros & Developers. It's quick & easy.

the lowest number of comparisons in string matching

P: n/a
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

Sep 22 '06 #1
Share this Question
Share on Google+
2 Replies


P: n/a
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

Sep 22 '06 #2

P: n/a
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)
Sep 22 '06 #3

This discussion thread is closed

Replies have been disabled for this discussion.