codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
$a = 'ABCDEF1GHIJKL2ABCDEFGHIJKL3X4DEFGHI'; # 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";
Private
[
?
]
Run code
Submit