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

You would inspect characters multiple times only in a very naive implementation of Boyer-Moore. The Galil Rule[0] fixes this and is also required for proving linear worst-case runtime.

[0] https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_sea...



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

Search: