[a1369209993]

> (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).

[a1369209993]

> 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.

[falserum]

Thanks.

Good to know that there was no repealment for Cunningham’s law.