sub compress {
    my $uncompressed = shift;

    
    my $dict_size = 256;
    my %dictionary = map {chr $_ => chr $_} 0..$dict_size-1;

    my $w = "";
    my @result;
    foreach my $c (split '', $uncompressed) {
        my $wc = $w . $c;
        if (exists $dictionary{$wc}) {
            $w = $wc;
        } else {
            push @result, $dictionary{$w};
            
            $dictionary{$wc} = $dict_size;
            $dict_size++;
            $w = $c;
        }
    }

    
    if ($w) {
        push @result, $dictionary{$w};
    }
    return @result;
}


sub decompress {
    my @compressed = @_;

    
    my $dict_size = 256;
    my %dictionary = map {chr $_ => chr $_} 0..$dict_size-1;

    my $w = shift @compressed;
    my $result = $w;
    foreach my $k (@compressed) {
        my $entry;
        if (exists $dictionary{$k}) {
            $entry = $dictionary{$k};
        } elsif ($k == $dict_size) {
            $entry = $w . substr($w,0,1);
        } else {
            die "Bad compressed k: $k";
        }
        $result .= $entry;

        
        $dictionary{$dict_size} = $w . substr($entry,0,1);
        $dict_size++;

        $w = $entry;
    }
    return $result;
}


my @compressed = compress('TOBEORNOTTOBEORTOBEORNOT');
print "@compressed\n";
my $decompressed = decompress(@compressed);
print "$decompressed\n";