Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.

 help



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 :-)




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: