Fastest String Search Algorithm.

[Wilco Dijkstra]

Hi Amit,

> I wrote a program to test my algorithm with strstr(). The text to search is
> around 60 KB and the pattern is around 1.3 KB.
> 
> The surprise is that """""strstr() failed to find the pattern."""""

It's possible you have an old GLIBC - I remember a strstr bug years ago where
it failed to match very large patterns.

Anyway, the generic strstr in a recent GLIBC is over 1000 times faster on this test.

Basically you don't want to compare with ancient Boyer-Moore or KMP (which AFAIK
nobody uses in the real world) but with the best modern algorithms. Modern string
algorithms are fast due to not inspecting every single character. They skip most of
the input by jumping ahead by the size of the pattern after a mismatch. So perhaps
counterintuitively, they become much faster with a larger search pattern.

Cheers,
Wilco