4 ms·

Is this faster than Aho-Corasick? https://en.m.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm https://en.m.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorit...

• hvdijk 5y ago
  It solves a slightly different problem, searching for one substring instead of searching for one of many, so it would not be fair to compare the two.
  • AlbertoGP 5y ago
    Yes, and if you need the best of both there is the Commentz-Walter algorithm from 1979: > Like the Aho–Corasick string matching algorithm, it can search for multiple patterns at once. It combines ideas from Aho–Corasick with the fast matching of the Boyer–Moore string search algorithm. For a text of length n and maximum pattern length of m, its worst-case running time is O(m·n), though the average case is often much better. > GNU grep implements a string matching algorithm very similar to Commentz-Walter. https://en.wikipedia.org/wiki/Commentz-Walter_algorithm https://en.wikipedia.org/wiki/Commentz-Walter_algorithm
    • burntsushi 5y ago
      Commentz-Walter doesn't work that well in practice. As you add more patterns, the likelihood that there is any meaningful byte skipping goes way down. So it might be useful for a small number of patterns, but at that point, there are vectorized algorithms that will do (a lot) better. (Like Teddy from Hyperscan.)
      • AlbertoGP 5y ago
        Thank you very much for this reply. I was considering implementing it for a program I’m writing, but in light of that it’s clearly not worth it.