# 
# Marco's updated performance table just informed me that my algorithm
# still fails with adjoining longest subpatterns (as in '123123'). I
# thought that I had fixed that already but obviously I had still one
# other index wrong by one (in the while() condition).

sub repeated_substring {
    use integer;
    my $string  = shift;
    my $len     = length($string);
    my $longest = $len / 2;
    my $substring;
    my $offset = 1;
    my $optimize;
    LENGTH: for my $l (1 .. $longest) {
        my $num = $len - $l - 1;
        while ((local $_ = $offset) <= $num) {
            my $sub = substr $string, $_ - 1, $l;
            # once the substring is longer than the string
            # we compare it against, we can last out because
            # it can't match
            last LENGTH if length($sub) > length($string) - $_ - $l + 1;
            index($string, $sub, $_ + $l - 1) != -1 
                and $substring = $sub
                and $offset = $_
                and ($optimize = $l > 15, next LENGTH);
                
            if ($optimize) {
                my $s = substr($sub, $l / 2);
                index($string, $s, $_ + $l - 1) == -1
                    and $offset += $l / 2
                    and next;
                $offset++;
            } else {
                $offset++;
            }
        }
        # we didn't find a substring of given length:
        # that means we can't find a substring of a bigger length either
        last if length($substring) < $l;
    } 
    return $substring;
}
