3 ms·
You don't really need the full Aho Corasick algorithm to determine set membership of a string. A simple Trie structure made of the set of strings would suffice
by MattPalmer1086 4y ago
You don't really need the full Aho Corasick algorithm to determine set membership of a string.
A simple Trie structure made of the set of strings would suffice.
- pimlottc 4y agoNo, and it doesn't work for exactly this situation anyway, since you only want complete string matches here (e.g. "paws" shouldn't match), but I thought it was an interesting related problem.
- jeffrallen 4y agoThere's no way the cache thrashing of walking a trie would cost less than the integer compares the author used.
- yakubin 4y agoNot just cache, but also the branch mispredictions while walking a trie.
- scotty79 4y agoSince the trie is static it could be pregenerated and held in small static array that might fit in a cache line ... I think. I don't really know this stuff. But still probably would be slower especially if there aren't many misses that could be quickly rejected by the trie.
- MattPalmer1086 4y agoYes, for a small set of strings, which is the problem he is solving, you are almost certainly right.