Re: the lowest number of comparisons in string matching

"laura" <laura.brandusan@xxxxxxxxx> writes:
The lowest number (theoretical) is m-n+1, but as far as I know no
algorithm has achieved this limit.

Michal Nazarewicz wrote:
How come m-n+1? The lowest number in the worst case (when the pattern
is located in the last place you are looking at) is m (the length of
the string).

sjdevnull@xxxxxxxxx writes:
(pattern string aka "needle" is length n, string to be searched aka
"haystack" is length m)

A needle of length n can't begin after position m-n in the haystack.

So then the lowest number of comparisons is m-n+1 if needle is not
found in haystack and m if it's there, correct?

--
Best regards, _ _
.o. | Liege of Serenly Enlightened Majesty of o' \,=./ `o
..o | Computer Science, Michal "mina86" Nazarewicz (o o)
ooo +--<mina86*tlen.pl>--<jid:mina86*jabber.org>--ooO--(_)--Ooo--
.

Relevant Pages

  • RE: Currency Field Format Correction
    ... Function SF_removeAllOnce(ByVal Haystack As String, ByVal Needle As String) ... Fieldname]) and run the query. ...
    (microsoft.public.access.modulesdaovba)
  • Re: PHP global namespace clogged up
    ... -string strchr(string haystack, string needle) ... int strpos(string haystack, string needel ): ...
    (comp.lang.php)
  • Re: Really hardcore question about PHP needed :)
    ... ton of lead v ton of feathers...still a ton, ... |> $haystack in each function. ... | $needle. ... variables that a test taker should know? ...
    (comp.lang.php)
  • Re: And the healthcare professional SAID WHAT????
    ... group would be much like finding a needle in a haystack. ... These are all things we espouse. ... From the way some people have described their doctors' reactions, I'm wondering if doctors truly do not believe normal numbers can be attained no matter what a person does, even with low carbing--until someone shows up in their offices who has. ...
    (alt.support.diabetes)
  • Documentation on strpos
    ... "Returns the numeric position of the first occurrence of needle in the ... full string as the needle parameter and the entire string will be used." ... I find the reference to "strrpos" confusing, ... haystack string." ...
    (comp.lang.php)