While significantly faster than the OP's, I believe it suffers from some of the same scalability issues. That's one thing I hate about regular expressions: determining the complexity of an algorithm built on them tends to be very difficult.
Anyway, that also suffers from another problem. Try it with
my @a = ('a' . 'X' x 32768, 'a' . 'O' x 32768);
and you'll get an error:
Quantifier in {,} bigger than 32766 in regex; marked by <-- HERE in m/
+(.{ <-- HERE 32767}).*\0.*\1/
-sauoq
"My two cents aren't worth a dime.";