

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

    # Calculate the length for reuse 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));

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

                # Bail if this index requires a match past the end of the string
                last if ($word_len + $repeat_idx) > $str_len;
            }

            # Record this matched substring
            $longest = substr($str, $idx, $word_len-1);
            # We don't need to start with any of the chars in this word anymore
            $idx += $word_len - 1;
        }
    }

    return $longest;
}

__END__
The technique is pretty straightforward.  Start looking for the minimum
length reasonable repeated pair (2 or more characters) and if a repeated
pair is found, see if the pair still match if each "word" is grown by
one character.  Keep adding characters until the set ceases to match.

At this point there is no need to start testing any of the characters
that were in the first pair (since you've already found the longest
match in that string of characters) so start the search just after the
first "word" of the pair just found.  Also, smaller matches than the
length of the pair just found can now be ignored which saves some tests.

Testing can stop once we get to a position in the string that is twice
the current "word" length from the end of the string.  We'd be wasting
our time if we checked any further since there wouldn't be enough
characters left in the string for a repeated pair.

This function seems to do alright for itself.  I tested it against a
68852 character string (the contents of a 67k image) and it found the
longest repeated string of 84 characters in just under 8 seconds.  Thats
about 8800 characters per second on my machine.

I thought I could save time by changing the code that tries longer and
longer pairs from:

    while (substr($str, $idx, $word_len) eq
           substr($str, $repeat_idx, $word_len)) {

to:

    while (substr($str, $idx + $word_len - 1, 1) eq
           substr($str, $repeat_idx + $word_len - 1, 1)) {

with the idea that it would be faster to compare the single characters
after the initial match, than comparing each increasingly larger
"word".  However Benchmark told me it was actually a lot slower.  I
chalk that up to C code in 'substr' being much faster than my perl code.

-- 
Garth Winter Webb <garth@perijove.com>
-- 
Garth Winter Webb <garth@perijove.com>
