Hacker News Reader

Ok, so why not use a fast memcmp on the first 4-8 chars of the pattern to identify any potential match and once found, work from there to verify if a full match exists?

This is essentially what I have have been doing for years and it is very simple. I'm sure it is not always the fastest but it's not too shabby either in the real world.

View on HN

Probably very effective for shorter patterns. Two reasons to use more complex algorithms for longer patterns:

1. Linearity - the naive approach is quadratic on worst case data (imagine searching for 100 0's in a text of 0's).

2. Sublinearity - sublinear search algorithms skip over text that cannot match. They typically have the somewhat counter-intuitive property that they get much faster the longer the pattern is. So long patterns will be faster using a sub linear search algorithm.

Yes but longer patterns are kind of an outlier.

Most of the everyday searching and parsing that I end up doing involves relatively short patterns. Maybe I am an outlier :-)

Reply on news.ycombinator.com