import java.io.*;
public class LZW {
public static void dekoduoja(String input, String output){
try{
int suma=0;
OutputStream os=new FileOutputStream(output);
InputStream is=new FileInputStream(input);
BitInput bi=new BitInput(is);
String[] zodynas=new String[2048];
int i=0;
int bits=0;
zodynas[1]=(char)10+"";
zodynas[2]=(char)13+"";
zodynas[3]=(char)9+"";
for (int n=32;n<=126;n++){
zodynas[n-28]=""+(char)n;
i=n-27;
}
for(int r=0;Math.pow(2, r)<i;r++){
bits=r+1;
}
String w="";
int sk=bi.readBits(bits);
suma+=bits;
for(int j=0;j<i;j++){
if(j==(sk)){
os.write(zodynas[j].charAt(0));
w+=zodynas[j];
break;
}
}
for(int r=0;Math.pow(2, r)<i;r++){
bits=r+1;
}
int c=bi.readBits(bits);
String entry="";
while (c!=0){
suma+=bits;
if (c==0){return;}
else if (c<i){entry=zodynas[c];}
else if (c==i){entry=w;}
else{System.out.println("Klaida!!!!!: "+c); return;}
os.write(entry.getBytes());
//System.out.println(entry+" | "+i+" "+suma);
//sleep(500);
zodynas[i]=w+entry.charAt(0);
i++;
w=entry;
for(int r=0;Math.pow(2, r)<=i;r++){
bits=r+1;
}
c=bi.readBits(bits);
}
}catch(IOException e){System.out.println(e);}
}
public static void spaudzia(String input, String output){
try{
OutputStream os=new FileOutputStream(output);
BitOutput bo=new BitOutput(os);
InputStream is=new FileInputStream(input);
String[] zodynas=new String[2048];
int bits;
int c;
int i=0;
int suma=0;
zodynas[1]=(char)10+"";
zodynas[2]=(char)13+"";
zodynas[3]=(char)9+"";
for (int n=32;n<=126;n++){
zodynas[n-28]=""+(char)n;
i=n-27;
}
String w="";
is = new FileInputStream(input);
boolean radom=false;
while ((c=is.read())!= -1) {
for (int n=0;n<i;n++){
if ((w+(char)c).equals(zodynas[n])){w=w+(char)c; radom=true; break;}
radom=false;
}
if(!radom){
zodynas[i]=w+(char)c;
for (int n=0;n<i;n++){
if (w.equals(zodynas[n])){
for(int m=0;;m++){
bits=(int)Math.pow(2, m);
if (bits>=i){bits=m;break;}
}
bo.writeBits(n, bits);
suma+=bits;
}
}
w=""+(char)c;
i++;
}
}
for(double m=0;;m++){
bits=(int)Math.pow(2, m);
if (bits>=i){bits=(int)m;break;}
}
for (int n=0;n<i;n++){
if (w.equals(zodynas[n])){
bo.writeBits(n, bits);
suma+=bits;
break;
}
}
for(double m=0;;m++){
bits=(int)Math.pow(2, m);
if (bits>=i){bits=(int)m;break;}
}
bo.writeBits(0,bits);
suma+=bits;
int k=8-suma%8;
if(k==8){k=0;}
bo.writeBits(0,k);
suma+=k;
}catch(IOException e){System.out.println(e);}
}
public static void main(String[] args){
spaudzia("in.txt","in.lzw");
dekoduoja("in.lzw","final.txt");
}
}