#!/usr/bin/perl
use warnings;
use strict;

# Find the longest repeated substring of $stirng

# DESCRIPTION:
#
# Everything tries to leverage the fact that a repeated substring of
# length L is made up of repeated substrings of lengths < L.
#
# - The array @valid_starts keeps track of where previuos repeated
# substrings have occured, so that we don't check useless posititons.
#
# - we use a hash to avoid re checknig the same pattern twice
#
# - we always remeber the longest string found so far; if we try to
# find repeats of length L and can't we know that the most recently
# found repeated (ie the value of $longest_so_far) is the (rightmost)
# longest repeated substring and we're done.
#
# - when checking to see if a substring appears later on in the input
# text we use a regexp, the original version did it by hand, but
# perl's re engine is faster than anything you can write with pure
# perl.

sub repeated_substring {
    my $string = shift;
    study $string;
    my $string_length = length($string);
    my $max_length = int($string_length / 2);
    # initially every spot is valid
    my @valid_starts = (1) x $string_length;
    my $longest_so_far_start = -1;
    my $longest_so_far_length = -1;
    # vars we use
    my %patterns = ();

    for (my $length = 1; $length <= $max_length; $length++) {
        my $found_something = 0;
        my $pattern;
        # putting this here (where it should go) stops constitution at
        # the 5th iteration...
        #my %patterns = ();
      OFFSET_LOOP:
        for (my $offset = 0; $offset <= $string_length - $length; $offset++) {
            $offset++ while (! $valid_starts[$offset]);
            $pattern = substr $string, $offset, $length;
            next OFFSET_LOOP if $patterns{$pattern}++;
            # we want to see if $pattern appears later on in the text
            pos $string = $offset + $length;
            # we go to regexps here because perl's internal bump ahead
            # is faster than anything we could make.
            if ($string =~ /\Q$pattern\E/g) {
                $longest_so_far_start  = pos($string) - $length;
                $longest_so_far_length = $length;
                $found_something = 1;
            } else {
                $valid_starts[$offset] = 0;
                if ($offset > 1) {
                    # why the next bit is legit:
                    # - every repeated substring is made up of
                    # repeated substrings.
                    # - we DON'T have a repeated substring at $offset.
                    # - Therefore: the substring starting at $offset - 1
                    # and of length $length + 1 (which is the string
                    # we would check next time around) is made up of
                    # some char and a non repeated substring, so it
                    # can't be a repeated substring.
                    $valid_starts[$offset - 1] = 0;
                }
            }
        }
        if ($found_something == 0) {
            goto DONE;
        }
    }
  DONE:
    return substr $string, $longest_so_far_start, $longest_so_far_length;
}

1;
