#input
#>in
#aabbeecbabebe



#!/usr/bin/perl 

use strict;

use Data::Dumper;
use Getopt::Long;


my ($help,$in,$out);
GetOptions ("i=s" => \$in,  # input 
                        "h" => \$help,     # help
                        "o=s" => \$out,
            );
                        
if($help || !$in){
  print "Usage:\n\n";
  print "\t-i\tinput - single fasta file(it only uses the first fasta seq)\n";
  print "\t-o\toutput - output file <optional>\n";
  exit(0);
}


my $hash_seq = _read_fasta(in => $in);

foreach my $key (keys %{$hash_seq}){
  my @suftab = _sort_suffixes(array => $hash_seq->{$key});
  my ($height,$sufinv) =_kasai(suftab => \@suftab,
                               string => $hash_seq->{$key});
  print "Hight:@{$height}\n\nRank:@{$sufinv}\n\nPosition:@suftab\n\n";
}

#########################################################
#    Subs...
#########################################################

sub _read_fasta {

my %arg = @_;

open (IN, "<", $arg{in}) || die "$!";

my %hash =();
my ($head, $t) = (undef,0);
my @seq = ();
while(<IN>){
  chomp;
  if (/>(.*?)/){
    last if $t ==1;
    if (defined $head){
      push(@seq,"z");
      $hash{$head} = \@seq ;
    }
    $head=$1;
    @seq = ();
    $t++;
  }
  else{
	my @tmp = split('',$_);
    push(@seq,@tmp);
  }
}
if (defined $head){
  push(@seq,"z");
  $hash{$head} = \@seq ;
}
close IN;
return \%hash;
}


sub _kasai {

my %arg = @_;

my @sufinv = ();
for (0..$#{$arg{string}}){
	$sufinv[$arg{suftab}->[$_]] = $_;
}
my $h = 0;

my @height = ();
for (0..$#{$arg{string}}){ 
	if($sufinv[$_] >= 1){
		my $k = $arg{suftab}->[$sufinv[$_] - 1];
		while($arg{string}->[$_ + $h] eq $arg{string}->[$k + $h]){
			$h++;
		}
		$height[$sufinv[$_]] = $h;
		if($h>0){
			$h--;
		}
		else{
			$h = 0;
		}
	}
}
return (\@height,\@sufinv);
}


sub _sort_suffixes {

my %arg = @_;

return map  { $_->[ 0 ] } sort { $a->[ 1 ] cmp $b->[ 1 ] } map  { [ $_, join q{}, @{$arg{array}}[$_..$#{$arg{array}} ] ] }   0 .. $#{$arg{array}}; # solution provided by Johngg

}