the lowest number of comparisons in string matching

From: "laura" <laura.brandusan@xxxxxxxxx>
Date: 22 Sep 2006 05:54:06 -0700

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

.

Follow-Ups:
- Re: the lowest number of comparisons in string matching
  - From: Walter Roberson

Prev by Date: Re: Re:[OT] File read error win9x winNT
Next by Date: Re: strange getch+kbhit behaviour
Previous by thread: Merge Sort in C - array output is same as input after sort routine completes
Next by thread: Re: the lowest number of comparisons in string matching
Index(es):
- Date
- Thread

Relevant Pages

the lowest number of comparisons in string matching
... comparison for the string matching problem. ... I know that the complexity is liniar in the length of the strings, ... algorithm has achieved this limit. ... (where m is the lenght of the text and n is the length of the pattern). ...
(comp.theory)
the lowest number of comparisons in string matching
... comparison for the string matching problem. ... I know that the complexity is liniar in the length of the strings, ... algorithm has achieved this limit. ... (where m is the lenght of the text and n is the length of the pattern). ...
(sci.math)
the lowest number of comparisons in string matching
... comparison for the string matching problem. ... I know that the complexity is liniar in the length of the strings, ... algorithm has achieved this limit. ... (where m is the lenght of the text and n is the length of the pattern). ...
(sci.math.research)
the lowest number of comparisons in string matching
... comparison for the string matching problem. ... I know that the complexity is liniar in the length of the strings, ... algorithm has achieved this limit. ... (where m is the lenght of the text and n is the length of the pattern). ...
(comp.programming)
Re: FUD about CGD and GBDE
... >government has approved the use of AES with 256 bit keys for very ... that stress on the algorithm and maintain 256 bits of margin. ... I don't seriously think that either of CGD or GBDE will be broken ... The first reason is that it adds complexity. ...
(freebsd-hackers)