# 
# As Douglas Palmer pointed out, there was a problem with the last
# solution I posted, namely, that it would give up too soon.  Longer
# repeated matches at the end of the string would be ignored.  Here is an
# update that solves that problem, but is about 8% slower:


sub repeated_substring {
    my ($str) = @_;
    my $longest;
    my $word_len = 2;

    # Calculate the length for later.
    my $str_len = length($str);

    # Test until our index requires a match beyond the end of the string
    for (my $idx=0; $idx<=($str_len - 2*$word_len); $idx++) {
        my $test = substr($str, $idx, $word_len);

        # See if this string is repeated later on
        my $repeat_idx = index($str, $test, ($idx+$word_len-1));

        # If it is then try to lengthen the match until it fails.
        unless ($repeat_idx == -1) {
            while (1) {
                if (substr($str, $idx, $word_len+1) eq
                    substr($str, $repeat_idx, $word_len+1)) {

                    $word_len++;
                } else {
                    # See if we can find an other match for this later in the
                    # string
                    $repeat_idx = index($str,
                                        substr($str, $idx, $word_len+1),
                                        $repeat_idx + $word_len);

                    last if $repeat_idx == -1
                }

                # Make sure we don't sneak up on the beginning of the repeated
                # string
                $repeat_idx += $word_len if ($idx + $word_len >= $repeat_idx);
            }

            # Record this matched substring
            $longest = substr($str, $idx, $word_len);

            # Increase the size of the smallest word we'll consider
            $word_len++;
        }
    }

    return $longest;
}

