sub repeated_substring {
  my $str = shift() . '\0';  # adding an extra char avoids some edge cases
  my @letters = split //, $str;
  
  # $digraph_poses{} is a hash mapping two-character substrings to a list of
  # every position at which they occur.
  my %digraph_poses = ();
  for my $i (0 .. $#letters - 1) {
    push @{$digraph_poses{substr($str,$i,2)}}, $i;
  }

  # Any longest string is going to have to pass through $j or be entirely to
  # the left of it.
  my $j = $#letters - 1;

  # The best string found yet starts at $first_pos and is $max_length long.
  my $max_length = 0;
  my $first_pos = 0;

  # We work backwards through the string, purely for historical reasons.
  while ($j >= 0) {
    # Find all earlier substrings that could overlap this one
    for my $i (@{$digraph_poses{substr($str,$j,2)}}) {
      last if ($i >= $j-1);               # too late

      # All we know at this point is that $i and $i+1 match $j and $j+1.  Now
      # extend the matchingness in both directions.

      # See how far forward this one extends from $i/$j.
      my ($i2, $j2);
      for ($i2 = $i + 2, $j2 = $j + 2;
           $i2 < $j && $letters[$i2] eq $letters[$j2];
           ++$i2, ++$j2) {
      }
      my $extent_forward = $i2;

      # See how far backwards it extends.  $needed is how much
      # matching we need to beat $max_length; we test it all at once
      # since the substr equality comparison seems to be faster than
      # going character by character.
      my $needed = $max_length + 1 - ($i2 - $i);
      $needed = 0 if $needed <= 0;
      next if $j - $needed < $extent_forward; # disallow overlap
      if (substr( $str, $i - $needed, $needed ) eq
          substr( $str, $j - $needed, $needed )) {
        # This is a new longest substring; now see how much further
        # we can extend it.
        for ($i2 = $i - $needed - 1, $j2 = $j - $needed - 1;
             $i2 >= 0 && $j2 >= $extent_forward && $letters[$i2] eq $letters[$j2];
             --$i2, --$j2) {}
        $first_pos = $i2 + 1;
        $max_length = $extent_forward - $first_pos;
      }
    }
    $j -= ($max_length+1);
  }

  # We assumed the maximal repeated substring would be at least 2 characters long;
  # if it's only 1, we have to find it in a separate pass here.
  if ($max_length < 2) {
    my %seen = ();
    for my $i (0..$#letters) {
      if (defined $seen{$letters[$i]}) {
        return substr( $str, $i, 1 );
      } else {
        $seen{$letters[$i]} = 1;
      }
    }
    return "";
  }

  return substr( $str, $first_pos, $max_length );
}