#!/usr/bin/perl
use LWP::Simple;
use Time::HiRes qw(time);

my $data = shift || get("http://www.dfan.org/constitution.txt") || get("http://www.ibiblio.org/gutenberg/etext97/shndy10.txt");

my $then = time;
print "Result:\n------\n", maxsub($data), "\n------\n";
print time - $then, "\n";


sub repeated_substring
{
  my $len = length($_[0]);

  my ($best, $bestlen) = ("", 0);

  my ($left, $leftlen, $rightpos);
  for (my $leftstart = 0; $leftstart <= $len - 2 * ($bestlen+1); $leftstart++)
  {
    $rightpos = $leftstart + ($leftlen = 1 + $bestlen);
    $left = substr($_[0], $leftstart, $leftlen);

    while (($rightpos = index($_[0], $left, $rightpos)) >= 0)
    {
      $best = $left, $bestlen = $leftlen if $leftlen > $bestlen;
      $left = substr($_[0], $leftstart, ++$leftlen);
      unless ($leftstart + $leftlen > $rightpos)   # Non-overlapping
      {
        redo if index($_[0], $left, $rightpos) >= 0;
      }
      # This is where to capture "best so far"
      $rightpos += $leftlen;
    }
  }
  return $best;
}

__END__

The algorithm is pretty ordinary.  We march along the string starting
from each character position in turn, generating successively longer
substrings from that point and iterating through any and all matches
for each substring occurring in the main string after the end of the
substring.  

Everything else is just optimization; we don't continue searching in
the string past a point where no repeated substring could be longer 
than the best one found so far.  We start the candidate substring
out at a length equal to the length of the best one found so far,
plus one.

