[jekub]

Nop, the article is false about this. The optimal algorithm is O(n) as you can make a simple regular expression that is the Kleene star of an or of all the words in your dictionary to match the input. This is allowed as you can choose how to implement the dictionary, it don’t take more space than a trie and match in linear time as it can be compiled to an NFA or a DFA.

[bonzini]

The DFA is O(n) with up to exponential time spent upfront (and exponential space usage too). The exact complexity for the NFA with the regex you suggest depends on how the NFA is built, but it is at least O(n^2) worst case because you can easily build a case with n active states. Likewise for the lazy DFA.