2 ms·
This is incorrect, under deliriums pedantic interpretation of space complexity. Some regular expressions require one to accept a certain number of examples of a
by jmpeax 13y ago
This is incorrect, under deliriums pedantic interpretation of space complexity. Some regular expressions require one to accept a certain number of examples of a character. This means that storage space for the count is required, which scales logarithmically in the count.
- repsilat 13y agoThis is why my comment began with the words "particular, individual". A regex like (1{5}0{3})\* can be implemented in constant space, but a language like matches(n, m, string): return matches((1{n}0{m})\*, string) cannot. Just think about it -- the former is just a DFA, and so of course you can do it in constant space (provided your input stream is abstracted away, or you use a TM.