LZW

Alg.cpp

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>

using namespace std;

bool contains(map<string, int> dic, int x) {
    for (auto i:dic) {
        if (i.second == x) {
            return true;
        }
    }
    return false;
}

string getBin(int n, int size) {
    string res = "";
    for (int i = 0; i < size; i++) {
        if (n % 2 == 0) {
            res += "0";
        }else {
            res += "1";
        }
        n /= 2;
    }
    reverse(res.begin(), res.end());
    return res;
}

string getBinCode(vector<int> code, map<string, int> dic, int count) {
    string bin;
    for (int i = 0; i < code.size(); i++) {
        bin += getBin(code[i], ceil(log2(count)));
        count++;
    }
    return bin;
}

vector<int> encode(string word, map<string, int> dic) {
    vector<int> code;
    int count = dic.size();
    string x = dic.begin()->first;
    int n = word.size();
    for (int i = 1; i < n; i++) {
        string xy = x + word[i];
        if (dic.find(xy) != dic.end()) {
            x = xy;
            continue;
        }
        dic[xy] = count;
        count++;
        code.push_back(dic[x]);
        x = word[i];
    }
    code.push_back(dic[x]);       
    return code;
}

string decode(vector<int> code, map<string, int> dic) {
    int count = dic.size();
    string x;
    for (auto i: dic) {
    	if (i.second == code[0]) {
    		x = i.first;
    		break;
    	}
    }
    string dec = x;
    string xy = "";
    map<string, int>::iterator it;
        for (int i = 1; i < code.size(); i++) {
            for (it = dic.begin(); it != dic.end(); it++) {
                if (contains(dic, code[i])) {
                    if (it->second == code[i]) {
                        xy = x + it->first[0];
                        dic[xy] = count;
                    	count++;
                    	dec += it->first;
                    	x = it->first;
                    	break;
                    }
                }else{
                    string word;
                    for (auto i:dic) {
                        if (i.second == dic[x]) {
                            word = i.first + i.first[0];
                        }
                    }
                    dic[word] = count;
                    count++;
                    dec += word;
                    x = word;
                    break;
                }
            }
        }
    return dec;
}


int main()
{
    // string str = "abacabadabacabae";
    // string str = "abdabccabcdab";
    string str = "011011100001010100010101010";
    // map<string, int> dic = {{"a", 0}, {"b", 1}, {"c", 2}, {"d", 3}, {"e", 4}};
    map<string, int> dic = {{"0", 0}, {"1", 1}};
    vector<int> code = {0, 1, 1, 2, 3, 0, 7, 2, 9, 4, 7, 4, 13, 9};
    // map<string, int> dic = {{"a", 0}, {"b", 1}, {"c", 2}, {"d", 3}};
    // vector<int> code = {0, 1, 3, 4, 2, 2, 7, 6, 1};
    
    // vector<int> code = encode(str, dic);
    string dec = decode(code, dic);
    // string bin = getBinCode(code, dic, dic.size());
    cout << dec << endl;
    // for (int i: code) {
    //     cout << i;
    // }
    return 0;
}

decode.cpp

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>

using namespace std;

string getBin(int n, int size) {
    string res = "";
    for (int i = 0; i < size; i++) {
        if (n % 2 == 0) {
            res += "0";
        }else {
            res += "1";
        }
        n /= 2;
    }
    reverse(res.begin(), res.end());
    return res;
}

int main()
{
    string str = "abacabadabacabae";
    // map<string, int> dic = {{"a", 0}, {"b", 1}, {"c", 2}, {"d", 3}, {"e", 4}};
    map<string, int> dic = {{"a", 0}, {"b", 1}};
    
    //vector<int> code;
    vector<int> code = {0, 2, 0};
    vector<string> bin;
    vector<string> res;
    int count = dic.size();
    int x = 0;
    string word = "";
    string xy = "";
    for (int y: code) {
        for (auto i: dic) {
            xy = word;
        	int c = 0;
            if (i.second == y) {
            	res.push_back(i.first);
            	word += i.first;
            	
                if (word.length() >= 2) {
                    for (char j : i.first) {
                        string s(1, j);
                        if (dic.find(xy + j) == dic.end()) {
                        	dic[xy + j] = count;
                        	count++;
                    		word = i.first;
                    		c ++;
                    		break;
                        }   
            	    }
                }
            }
            
        	if (c == 1) {
        	    break;
        	}
        	
            if (dic.find(word) == dic.end()) {
                	dic[word] = ++count;
            		word = i.first;
            }
            
        }
    }
    
    for (string i:res) {
        cout << i << " ";
    }