# In article <bckoir$pmo$1@post.home.lunix>,
# 	qotwdiscuss@ton.iguana.be (Ton Hospel) writes:
# I massaged the suffix trees a bit to make them into a real solution to 
# the problem: strings without overlap. I'm however not 100% sure that the
# code i use to avoid overlap is always right.

#! /usr/bin/perl -w
# Implements Ukkonen 1995
# Code is based on the description and pseudo code in
#  http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Suffix/
# However
# - our stringpositions are 0 based
# - We represent an edge as (first_ch, length) instead of (first_ch, last_ch)
# - We always add a terminator
#
# - Nodes are hash references mapping the first char 
#   of an outgoing edge to the edge itself
# - Edges are array references: [first_ch, length, target_node]

use strict;
use Scalar::Util qw(weaken);

# use lib "/home/ton/lib";
# use Debug qw(debug);
# use Data::Dumper;

# Infinity is used as edge length on leafs
use constant INFINITY => 1e5000;
# We (ab)use key "\xff\xff" to represent the suffix links
use constant SLINK    => "\xff\xff";

my ($s, $k, $txt);

# For debugging. Nicely draw the suffix tree
sub DrawTree {
    my ($s, $prefix) = @_;
    print "->", $s->{+SLINK} ? "+" : "*";
    $prefix .= "  ";
    my @keys = sort keys %$s;
    pop @keys if $keys[-1] eq SLINK;
    for (0..$#keys) {
        print "$prefix|\n$prefix+" if $_;
        my ($k1, $l1, $s1) = @{$s->{$keys[$_]}};
        if ($l1 == INFINITY) {
            # printf "--%s(%2d)\$\n", substr($txt, $k1), $k1;
            printf "--%s\$\n", substr($txt, $k1);
        } else {
            #printf "--%s(%2d)", substr($txt, $k1, $l1), $k1;
            #DrawTree($s1, $prefix . ($_ == $#keys ? " " : "|") . " "x(6+$l1));
            printf "--%s", substr($txt, $k1, $l1);
            DrawTree($s1,$prefix . ($_ == $#keys ? " " : "|") . " " x (2+$l1));
        }
    }
}

sub Update {
    my $i = shift;
    # (s, (k, i-1)) is the canonical reference pair for the active point
    my $old_root;
    my $chr = substr($txt, $i, 1);
    while (my $r = TestAndSplit($i-$k, $chr)) {
        $r->{$chr} = [$i, INFINITY];
        # build suffix-link active-path
        weaken($old_root->{+SLINK} = $r) if $old_root;
        $old_root = $r;
        $s = $s->{+SLINK};
        Canonize($i-$k);
    }
    weaken($old_root->{+SLINK} = $s) if $old_root;
}

sub TestAndSplit {
    my ($l, $t) = @_;
    return !$s->{$t} && $s unless $l;
    my ($k1, $l1, $s1)  = @{$s->{substr($txt, $k, 1)}};
    my $try = substr($txt, $k1 + $l, 1);
    return if $t eq $try;
    # s---->r---->s1
    my %r = ($try => [$k1 +$l, $l1-$l, $s1]);
    $s->{substr($txt, $k1, 1)} = [$k1, $l, \%r];
    return \%r;
}

sub Canonize {
    # s--->...
    my $l = shift || return;

    # find the t_k transition g'(s,(k1,l1))=s' from s
    my ($l1, $s1) = @{$s->{substr($txt, $k, 1)}}[1,2];
    # s--(k1,l1)-->s1
    while ($l1 <= $l) {
        # s--(k1,l1)-->s1--->...
        $k += $l1;  # remove |(k1,l1)| chars from front of (k,l)
        $l -= $l1;
        $s  = $s1;
        # s--(k1,l1)-->s1
        ($l1, $s1) = @{$s->{substr($txt, $k, 1)}}[1,2] if $l;
    }
}

# construct suffix tree for $txt[0..N-1]
# Giving a true argument adds the empty string as terminator
sub BuildTree {
    my $end_char = shift() ? length($txt) : length($txt)-1;
    # bottom or _|_
    my %bottom;
    my %root = (SLINK() => \%bottom);
    # Create edges for all chars from bottom to root
    $bottom{substr($txt, $_, 1)} ||= [$_, 1, \%root] for 0..$end_char;

    $s = \%root;
    $k = 0;
    for (0..$end_char) {
        # follow path from active-point
        Update($_);
        Canonize($_-$k+1);
    }
    # Get rid of bottom link
    delete $root{+SLINK};
    return \%root;
}

my ($best, $to);
sub lrs {
    my ($s, $depth) = @_;
    # Skip leafs
    return unless $s;
    for (keys %$s) {
        next if $_ eq SLINK;
        my ($l, $node) = @{$s->{$_}}[1,2];
        lrs($node, $depth+$l);
    }
    return if $best >= $depth;
    # You may already be a winner !
    # Only do the hard work if we can gain.
    my $min_k =  INFINITY;
    my $max_k = -INFINITY();
    for (keys %$s) {
        next if $_ eq SLINK;
        my $k = $s->{$_}[0];
        $min_k = $k if $k < $min_k;
        $max_k = $k if $k > $max_k;
    }
    
    $max_k -= $min_k;
    if ($max_k >= $depth) {
        $best = $depth;
        $to   = $min_k;
    } elsif ($max_k > $best) {
        # Oops, overlap. Reduce length
        $best = $max_k;
        $to   = $min_k;
    }
}

sub LongestRepeatedSubstring {
    my $tree = shift;
    $best = 0;
    $to   = 0;
    lrs($tree, 0);
    return substr($txt, $to-$best, $best);
}

sub repeated_substring {
    $txt = shift;
    return LongestRepeatedSubstring(BuildTree(1));
}

# debug(qw[Update TestAndSplit Canonize(d)]);

# Three ways of calling:
if (@ARGV) {
    if ($ARGV[0] =~ m![./]!) {
        # If the argument contains a . or /, guess it's a file
        open(my $fh, "<", $ARGV[0]) || die "Could not open $ARGV[0]: $!";
        my $text = do { local $/; <$fh> };
        print "LRS=<", repeated_substring($text), ">\n";
    } else {
        # Otherwise, assume the argument is a string
        $txt = shift;
        my $tree = BuildTree(1);
        print "LRS=<", LongestRepeatedSubstring($tree), ">\n";
        DrawTree($tree);
    }
} else {
    # Default string for basic sanity checking and demo
    $txt = "xabxac";
    my $tree = BuildTree;
    DrawTree($tree);
}
