3 ms·
See also: https://github.com/google/re2/blob/main/re2/bitstate.cc https://github.com/google/re2/blob/main/re2/bitstate.cc Although its space complexity is P*T,
by burntsushi 4y ago
See also: https://github.com/google/re2/blob/main/re2/bitstate.cc https://github.com/google/re2/blob/main/re2/bitstate.cc
Although its space complexity is P*T, which limits its use to small regexes/haystacks. It sounds like your claim is that your technique achieves a smaller space bound?
- hddqsb 4y agoYes. My proposed fix takes O(P * T) time and O(1) memory (but it only supports glob-style wildcards; it doesn't support repetition of specific characters / character classes / sub-patterns).
- burntsushi 4y agoAh gotya. An important clarification indeed. Thanka for that!
- deleted 4y ago[deleted]