On Sat, Jan 19, 2002 at 02:52:15PM +0000, Robin Houston wrote:
> Consider this subroutine:
>
> sub shrinkable ($) {
> my $str = shift;
> for my $i (1..length($str)) {
> return 1 if substr($str, $i) . substr($str, 0, $i) lt $str;
> }
> return 0;
> }
>
> So "foo" is not shrinkable, "bar" is shrinkable and so on.
> Intuitively, a string is shrinkable iff it can be split into
> two pieces $A.$B so that ("$B$A" lt "$A$B"). "bar" is shrinkable
> because you can split it into b,ar and ("arb" lt "bar").
>
> Can you write a regex which matches only shrinkable strings?
> No, you're not allowed to use embedded code constructs ;-)
/^ba/;
Or should the regex match all shrinkable strings as well? :)
Ronald
