# 
# Everyone seems to improve on his algorithm and so am I. It all seems to
# boil down to one mutation of the basically same algorithm by Cees'.

sub repeated_substring {
    use integer;
    my $string  = shift;
    my $len     = length($string);
    my $longest = $len / 2;
    my $substring;
    my $offset = 1;
    my $optimize;
    LENGTH: for my $l (1 .. $longest) {
        my $num = $len - $l - 1;
        # local $_ has purely historical reasons
        while ((local $_ = $offset) < $num) {
            my $sub = substr $string, $_ - 1, $l;
            # once the substring is longer than the string
            # we compare it against, we can last out because
            # it can't match
            last LENGTH if length($sub) > length($string) - $_ - $l + 1;
            index($string, $sub, $_ + $l - 1) != -1 
                and $substring = $sub
                and $offset = $_
                and ($optimize = $l > 15, next LENGTH);
            
            # The Cees-shortcut
            if ($optimize) {
                my $s = substr($sub, $l / 2);
                index($string, $s, $_ + $l - 1) == -1
                    and $offset += $l / 2
                    and next;
                $offset++;
            } else {
                $offset++;
            }
        }
        # we didn't find a substring of given length:
        # that means we can't find a substring of a bigger length either
        last if length($substring) < $l;
    } 
    return $substring;
}

__END__

Currently, optimization starts when a substring of 16 characters has
been found. This turned out to be the best number for my case.
Interesting to see that an uneven number of characters slows it down a
little.

I am currently interested to find out in about which O-class this
algorithm lies. It's hard to actually calculate it because of the many
conditional branches in it so I strive towards an empirical approach.
For a given imput measure the time to process it. On the left side is
the length in characters, on the right the time it took:

    26887          .141s
    319131        6.200s
    535593       14.776s
    1061420     122.628s

I want to add a few more cases and try to plot the graph. It looks a bit
like exponential to me right now. But such estimations can be
treacherous.

Tassilo
-- 
$_=q#",}])!JAPH!qq(tsuJ[{@"tnirp}3..0}_$;//::niam/s~=)]3[))_$-3(rellac(=_$({
pam{rekcahbus})(rekcah{lrePbus})(lreP{rehtonabus})!JAPH!qq(rehtona{tsuJbus#;
$_=reverse,s+(?<=sub).+q#q!'"qq.\t$&."'!#+sexisexiixesixeseg;y~\n~~dddd;eval

