the lowest number of comparisons in string matching

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 achieved this limit.

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

Thanks,
Laura

.

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.programming)
  • 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 achived this limit. ... (where m is the lenght of the text and n is the length of the pattern). ...
    (comp.lang.c)
  • 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)