Re: the lowest number of comparisons in string matching


Hi,

Which is the number of comparisons in the worst case?

thanks,
laura

Tor Myklebust wrote:
Tim Peters <tim.one@xxxxxxxxxxx> wrote:
[snip]
While it may not be immediately obvious, it's possible to construct an
essentially similar searcher for any pattern. Such constructions can be
found in any text covering finite automata and regular languages.

One can actually get away with fewer comparisons in the average case.
One technique for doing so is to read the pattern right-to-left as one
progresses through the text left-to-right --- see, for instance, the
Boyer-Moore algorithm and the modification due to Apostolico and
Giancarlo. (I seem to remember a paper, possibly by Rytter, in which a
sublinear lower bound and a slightly worse, but still sublinear,
algorithm for doing string matching were discussed. Again, everything
in the average case, since improving the worst-case behaviour is
hopeless.)

Tor Myklebust

.

Relevant Pages

  • Re: the lowest number of comparisons in string matching
    ... found in any text covering finite automata and regular languages. ... One technique for doing so is to read the pattern right-to-left as one ... Boyer-Moore algorithm and the modification due to Apostolico and ... sublinear lower bound and a slightly worse, but still sublinear, ...
    (comp.theory)
  • Re: Search through a (large) binary file.
    ... When the pattern is found, i need to know the offset, because then I'd ... like to read the 4 previous bytes (need the hex values). ... "Boyer-Moore Algorithm". ... Google will find example C# code for all three algorithms. ...
    (microsoft.public.dotnet.languages.csharp)