[yeputons]

The memory required to test. Moreover, we do not have random access to the string, we may only read one byte at a time and cannot go back. You may call it "streaming access".

More formally, we're talking about finite automata: https://en.wikipedia.org/wiki/Deterministic_finite_automaton