20 ms·
I wonder what, if any, is the advantage of this algorithm compared to forming a regex disjunction of the strings and compiling to DFA.
by kazinator 4y ago
I wonder what, if any, is the advantage of this algorithm compared to forming a regex disjunction of the strings and compiling to DFA.
- morelisp 4y agoThey do totally different things. A regex will tell you if the haystack contained any needle (and if you want, give you one specific one which depends on the engine/compilation). AC tells you all needles the haystack contained.
- burntsushi 4y agoThe reply you already got is kind of correct, but only in the sense of what is typically exposed at an API level. Most Aho-Corasick implementations have a way to provide all possible matches, even overlapping ones. Yet, most regex engines do not provide any way to return all possible matches. However, FSM-based regex engines can do that, if they want to, using largely the same structure as Aho-Corasick: keep a list of matching patterns for each match state. With that said, this would require treating each literal pattern as a distinct regex instead of doing 'pat0|pat1|..|patN'. But this is mostly just API stuff. Putting that aside, what I suspect to be the most essential difference is the construction algorithm itself. Building an Aho-Corasick NFA (or even DFA) is done in worst case linear time. But building a DFA through powerset construction takes worst case exponential time. Whether I'm actually right about that or not depends on whether the worst case bound for powerset construction remains as such when you know your input is just an alternation of literals. But certainly, if you take a general regex construction implementation and feed it a bunch of literals, the Aho-Corasick implementation is almost certainly going to come out on top. The former is more general and has more infrastructure that costs time and space.