#include <map>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
bool LZW_compression(vector<int> & d,string&s)
{
    typedef map<string,int> dict_type;
    typedef map<string,int>::value_type value_type;
   
    dict_type dict;
    //init the dictionary @add ansii charector to the dictionary
    int i;
    char str_2[2];
    str_2[1]=0;
    for(i=0;i<256;i++)
    {
        *str_2=i;
        dict.insert(value_type(str_2,i));
    }
   
    int j=0;
    string w;
    char k=s[j++];
    w=k;
   
    while(s[j])
    {
        k=s[j++];
        string str=w+k;
       
        if(dict.find(str)==dict.end())
        {
            dict.insert(value_type(str,i++));
            //output
            d.push_back(dict[w]);
            w=k;
        }
        else
        {
            w=str;
        }
       
    };
    d.push_back(dict[w]);
   
    return true;
}
 
bool LZW_decompression(string &d,vector<int>&s)
{
    typedef vector<string>::iterator pointor;
    vector<string> dict;
    //init the dictionary @add ansii charector to the dictionary
    int i;
    char str_2[2];
    str_2[1]=0;
    for(i=0;i<256;i++)
    {
        *str_2=i;
        dict.push_back(str_2);
    }
   
    int j=0;
    string old_str=dict[s[j]];
    d+=old_str;
    for(j=1;j<s.size();j++)
    {
        string now_str;
        if(s[j]<dict.size())
        {
            now_str=dict[s[j]];
        }
        else
        {
            now_str=old_str+old_str[0];
        }
        string str=old_str+now_str[0];
 
        if(find(dict.begin(),dict.end(),str)==dict.end())
        {
            dict.push_back(str);
        }
        d+=now_str;
        old_str=now_str;
    }
   
   
    return true;
}
int main()
{
    string s="aaaaaaaaaaaaaaaaaaaaaaaaa";
    vector<int> v;
    LZW_compression(v,s);
    for(int i=0;i<v.size();i++)
    {
        cout<<v[i]<<" ";
    }
    string s2;
    LZW_decompression(s2,v);
    cout<<endl<<s2;
    system("pause");
}