# 
# Hi,
# 
# Below is my implementation of the Expert Quiz #14.
# I've incoporated three optimisations.
# 
# #1: I only traverse till there is less than twice the largest
#     substring found so far.
# #2: I check only from the first largest substring found.
# #3: If the length of the new substring is more than 16 characters.
#     then check if the last half is found again. If it is, then,
#     move the starting counter to 1/2 of the substring + 1.
#     If it is not, then continue as always, but don;t perform the
#     check till you have crossed the 1/2 + 1 mark.
#     (Thanks Peter for this one.)
# 
# The program is relatively fast here, but I work on a server with more than
# 100 users.
# I'm hoping someone can benchmark my program for comparision.
# 
# Marco, hope your listening. :)
# 
# I don't have much time, or I would have written a better explanation.
# 
# This quiz has been really interesting.
# 
# bye,
# George P.


sub repeated_substring
    {
    my ($str, $len, $max, $do_opt);
    ($str) = @_;
    $len = length $str;
    my ($off, $char, $nsize, $try_str, $start, $end);
    $off = $start = $end = $do_opt = 0;
    $char = "";

    while ($end == 0)
        {
        my ($i);
        $nsize = length($char)+1;
        $max = $len-($nsize*2);
        $i=$start;
        if ($nsize >= $OPTNUM)
            {
            $do_opt-- if ($do_opt > 0);
            if ($do_opt <= 0)
                {
                my ($off_num, $size);
                $off_num = $i + int($nsize/2);
                $size = $i+$nsize-$off_num;
                $try_str = substr($str, $off_num, $size);
                if (index($str, $try_str, $i+1) == -1)
                    { $i=$off_num+1; }
                else
                    { $do_opt = $size-1; }
                }
            }
        for(; $i <= $max; $i++)
            {
            $try_str=substr($str,$i, $nsize);
            if (index($str, $try_str, $i+1) != -1)
                {
                $char = $try_str;
                $start = $i;
                last;
                }
            }
        if ($i == $max+1 || $i > $max)
            { $end = 1; }
        }
    return $char;
    }



