3 ms·
> (Solution complexity grows with length of the string within which we are searching) No it doesn't. It's something like '([^a]|a[^b]|a$)*'. In general it sca
by a1369209993 3y ago
> (Solution complexity grows with length of the string within which we are searching)
No it doesn't. It's something like '([^a]|a[^b]|a$)*'.
In general it scales like '([^a]|a([^b]|$)|ab([^c]|$)|abc([^d]|$)|...)*' (ie, quadratically with the length of the needle, if I haven't overlooked a optimization), but the complement of a regular language is regular, and fixed strings are always regular, so it's always a pure regular expression (including being independent of haystack length).
- falserum 3y agoThanks. Good to know that there was no repealment for Cunningham’s law.
- a1369209993 3y ago> It's something like '([^a]|a[^b]|a$)*'. And, proving that any curt correction of a silly error will likely contain its own silly error, I think that should actually be '^([^a]|a[^b]|a$)*$', since grep defaults to searching rather than matching.