$a = 'SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES';
# Indexing the matches
$l = length($a);
for( $i=0; $i<$l; $i++ ) {
$c = substr($a,$i,1);
$oldprice = 1E9;
@match = (0,0,0);
for( $j=$i-1; $j>=0; $j-- ) {
$flag=0;
for( $k=$l; $k>=$i+2; $k-- ) {
next if $f_match[$j+$k-$i];
if( substr($a,$i,$k-$i) eq substr($a,$j,$k-$i) ) {
$flag = 1; last;
}
}
if( $flag ) {
$price = (log(1+$i-$j)+log($k-$i)) / ($k-$i);
if( $price<$oldprice ) {
$oldprice = $price;
@match = ($j,$i,$k-$i);
}
}
}
if( $match[2] ) {
$j = $match[0]+$match[2];
$target[$j] = $match[1];
$length[$j] = $match[2];
$source[$match[1]] = $match[2];
for( $x=0; $x<$match[2]; $x++ ) { $f_match[$match[1]+$x]=1; }
$i += $match[2]-1;
}
}
$cs = ""; # compressed string
# Compressing the string, $a -> $cs
for( $i=0; $i<$l; $i++ ) {
if( $source[$i] ) {
$i += $source[$i]-1;
} else {
$c = substr($a,$i,1);
if( $target[$i] ) {
$cs .= sprintf( "<%s;%s>", $target[$i]-$i, $length[$i] );
}
$cs .= $c;
}
}
print $a, "\n";
print $cs,"\n";
$us = ""; # uncompressed string
# Decompressing $cs -> $us
undef @target;
undef @length;
for( $j=0; $j<length($cs); $j++ ) {
while(1) {
$i = length($us);
last unless $length[$i];
$us .= substr( $us, $target[$i]-$length[$i], $length[$i] );
}
$s = substr($cs,$j);
$c = substr($cs,$j,1);
if( $s=~/^<(\d+);(\d+)>/ ) {
$k = $1+$i; # + $1 + $2;
$target[$k] = $i;
$length[$k] = $2;
$j += length($&)-1;
} else {
$us .= $c;
}
}
print $us,"\n";