Re^3: Finding repeat sequences.

[hdb]

UPDATE: WARNING: the following code does not work in all circumstances. Sorry!

Here is a variant of tobyink's solution that uses index to look ahead when the current candidate string repeats and then enlengthens (is that an English word?) it accordingly.

sub find_substring
{
    my $input = shift;
    my $length = length $input;
    my $i = 0;
    my $possible;
    while( 1 ) { 
        $possible = substr $input, 0, $i+1; # increase length by 1
        $i = index $input, $possible, $i+1; # find next occurence of c
+andidate
        return $input if $i < 0;            # if not found return full
+ string => no repetition
        $possible = substr $input, 0, $i;   # this is the minimum leng
+th candidate
        return $possible if $input eq substr($possible x (1 + int($len
+gth / $i)), 0, $length); # success
    }
}

UPDATE: Eily's solution below Re^3: Finding repeat sequences. can be used to avoid the construction of the repeated string (as it is the same just with offset). Therefore, this works even better:

sub find_substring
{
  my $input = shift;
  my $length = length $input;
  my $i = 0;
  while( 1 ) { 
    $i = index( $input,  substr( $input, 0, $i+1 ), $i+1);
    return $input if $i < 0;
    return substr( $input, 0, $i) if substr( $input, $i ) eq substr($i
+nput, 0, $length - $i); 
  }
}