Yeah, a DFA that recognizes a regular language can easily be implemented with O(n) worst case behavior. My attitude is generally that one should use regexes fo

Yeah, a DFA that recognizes a regular language can easily be implemented with O(n) worst case behavior. My attitude is generally that one should use regexes for matching regular languages and if one needs a stack or even Turing completeness then handle that in code around the regex.