The algorithm works using more complex state tracking, but given the worst case of being in all states at once at a given point of the input, you're at O_space(

The algorithm works using more complex state tracking, but given the worst case of being in all states at once at a given point of the input, you're at O_space(len_regex), where the input string length still doesn't factor in at all.