#!/usr/bin/perl
use Modern::Perl '2011';
use autodie;

my $str = 'mississippi$';
my @suff; # hold suffixes
while ( $str ) {
	push @suff, $str;
	substr ( $str, 0, 1, '' );
}

# lexically ordered suffix array
my @indices = sort { $suff[$a] cmp $suff[$b] } 0 .. $#suff;

shift @indices; # remove $
for ( 0 .. $#indices ) {
	say $indices[$_]+1, ": ", $suff[ $indices[$_] ];
}

my $pattern = 'issi';

# find smallest index where pattern matches first n characters of suffix 
my $start = bsearch( \@indices, $pattern );
# get consecutive positions where pattern matches first n chars of suffix
my @positions;
for my $index ( $start .. $#indices ) {
	push @positions, $indices[ $index ] + 1 if $suff[ $indices[ $index ] ] =~ /^$pattern/;
}
# print results
say "\nPattern \"$pattern\" found at (position: suffix):";
for my $pos ( sort{ $a <=> $b } @positions ) {
	chop( my $s = $suff[ $pos - 1] );
	say "$pos: $s";
}

sub bsearch {
	my $mid;
	my ( $low, $high ) = ( 0, $#indices );
	while ( 1 ) {
		$mid = int( ( $low + $high ) / 2 );
		if( $suff[ $indices[ $mid ] ] =~ /^$pattern/ ) {
			return $mid;
		}
		if( $pattern lt $suff[ $indices[ $mid ] ] ) {
			$high = $mid - 1;
		}
		elsif( $pattern gt $suff[ $indices[ $mid ] ] ) {
			$low = $mid + 1;
		}
		return unless $low <= $high;
	}
	return "pattern not found in string!";
}

#output
abualiga:~$ ./suffixArray.pl
11: i$
8: ippi$
5: issippi$
2: ississippi$
1: mississippi$
10: pi$
9: ppi$
7: sippi$
4: sissippi$
6: ssippi$
3: ssissippi$

Pattern "issi" found at (position: suffix):
2: ississippi
5: issippi