The 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 t

The 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.