# 
# I know, I said I wouldn't post again... but I came up with a 
# great optimization :-)  I'm down to .05 seconds for the Constitution 
# and 28.4 seconds for Tristram on my machine... close to Cees.
# 
# [Cees' post arrived while I was testing this... and I see we 
# have basically the same optimization.  The different 
# implementations may be interesting though.  I tried lengths 
# ranging from 4 to 24 for the point at which the optimizer 
# should kick in and I settled on 16.] 
# 
# And thanks to Marco Baringer's test page for pointing out 
# I used to have a bug in handling certain overlapping strings.


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

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

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

    while ($skip = 1)        # Triggers syntax warning 
    {
      if ($optimizing)
      {
	# If last half of substring at current position
	# isn't anywhere in rest of string, we can skip
	# to 1 past its beginning
	my $half = $bestlen / 2;
	if (index($_[0], substr($left, $half, $half), $rightpos) < 0)
	{
	  $skip = $half + 1;
	  last;
	}
      }
      last unless ($rightpos = index($_[0], $left, $rightpos)) >= 0;

      if ($leftlen > $bestlen)
      {
	$best       = $left; 
	$bestlen    = $leftlen;
	$optimizing = $bestlen > 16;
      }
      $left = substr($_[0], $leftstart, ++$leftlen);

      $rightpos++ if $leftstart + $leftlen > $rightpos;  # Overlapping

      redo if index($_[0], $left, $rightpos) >= 0;

      $rightpos += $leftlen;
    }
    $leftstart += $skip;
  }
  return $best;
}

=for comment

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.

The main optimization is executed if $optimizing is true, which occurs
when the length of the current best match is more than 16 characters.
I chose this value after reading Devel::SmallProf dumps of the
unoptimized version and seeing how long various operations were
taking, then trying some candidates.  The optimization is that if the
last half of the candidate substring at the current position is not
found in the rest of the string, then we can skip forward to one
character past the beginning of that substring.  The longer the best
match found so far, the faster this works.

Suppose the current best match is of length 17, then we are testing
candidate solutions of length 18.  Here our current left starting
position is #1:

|_________ABCDEFGHIJKLMNOPQR____________________|
          1        2        3

If 'FGHIJ' is not found in the string starting at #3, we can
advance the left starting position to #2.

I decided not to try further division on the grounds of diminishing
returns; the more tests that are added in the loop, the more the time
will increase for cases where the optimization isn't effective.

=cut

