#include <iostream>
#include <string>
#include <sstream>
using namespace std;
int numGL;
struct LZ77 {
char distance;
char count;
char nextSym;
LZ77* next = 0;
LZ77(char a, char b, char c) {
this->distance = a;
this->count = b;
this->nextSym = c;
}
};
void addToStruct(LZ77 *& code, char distance, char count, char nextSym) {
if (code->next == 0) {
LZ77* New = new LZ77(distance, count, nextSym);
code->next = New;
}
else
{
addToStruct(code->next, distance, count, nextSym);
}
}
void LZ77Out(LZ77* code) {
if (code->next == 0)
return;
cout << (int)code->distance << "." << (int)code->count << "." << code->nextSym << endl;
LZ77Out(code->next);
}
int contains(string window, string key) {
stringstream ss;
string buf;
int index = -1;
if (key.size() == 2)
{
if (window.find(key) != string::npos) {
numGL = 2;
return window.find(key);
}
else {
return -1;
}
}
if (key.size() == 3) {
ss << key[0] << key[1];
ss >> buf;
ss = {};
if (window.find(buf) != string::npos) {
index = window.find(buf);
}
else {
index = -1;
}
if (index!=-1) {
buf += key[2];
if (window.find(buf) != string::npos) {
numGL = 3;
return window.find(buf);
}
else {
numGL = 2;
return index;
}
}
else {
buf = "";
ss << key[1] << key[2];
ss >> buf;
ss = {};
if (window.find(buf) != string::npos) {
numGL = 2;
return window.find(buf);
}
else {
index = -1;
}
}
}
return index;
}
LZ77 *encodeLZ77(string input) {
string window = to_string(input[0]-48);
string buf = "";
stringstream ss;
int index, temp = 0;
for (int a = 0; a < 3; a++) {
buf += input[a];
}
LZ77* code = new LZ77(0,0,input[0]);
for (int a = 1; true; a++) {
numGL = 0;
if (a == input.size())
break;
window += input[a];
if (buf.size() == 1) {
addToStruct(code,0, 0, input[a]);
}
if (contains(window, buf) != -1) {
index = window.size() - contains(window, buf);
addToStruct(code,index, numGL, input[a]);
}
else {
addToStruct(code,0,0,input[a+1]);
}
if (numGL == 3) {
for (int b = a; b < input.size(); b++) {
if (temp == 3)
break;
ss << input[b];
temp++;
}
buf = "";
ss >> buf;
buf = {};
}
if (numGL == 2) {
for (int b = a; b < input.size(); b++) {
if (temp == 2)
break;
ss << input[b];
temp++;
}
buf = "";
ss >> buf;
buf = {};
}
}
return code;
}
int main()
{
LZ77Out(encodeLZ77("0100001000000100001"));
}#include <iostream>
#include <string>
#include <string_view>
#include <forward_list>
#include <algorithm>
using namespace std;
struct CodeNode
{
unsigned char beg;
unsigned char len;
char ch;
};
bool push_shift (string& s, char c, size_t len) // return true if first symbol were erased
{
if (s.size() < len) {s.push_back(c); return false;}
move (next(s.begin()), s.end(), s.begin());
s.back() = c; return true;
}
forward_list<CodeNode> LZ77 (string_view s, size_t win_len = 255)
{
forward_list<CodeNode> res; auto it = res.before_begin();
string win, buf; win.reserve(win_len); buf.reserve(win_len);
CodeNode next; size_t saved_win_len = 0;
for (char c : s) {
buf.push_back(c);
size_t pos;
next.ch = c;
//cout<<win<<' '<<buf<<' '<<saved_win_len<<'\n';
if ((pos = win.rfind(buf)) != string::npos) {
next.beg = saved_win_len-pos; next.len = buf.size();
if ( push_shift (win, c, win_len) ) saved_win_len--; //shift
} else {
it = res.insert_after(it, next); buf.resize(0);
next.beg = 0; next.len = 0;
push_shift (win, c, win_len);
saved_win_len = win.size();
}
}
if (next.len != 0) {next.len--; res.insert_after(it, next);}
return res;
}
size_t LZ77length (const forward_list<CodeNode>& code) { // get length of original string
size_t len = 0;
for (const CodeNode& cn : code) len += cn.len+1;
return len;
}
size_t LZ77size (const forward_list<CodeNode>& code) { // get size of coded data
return sizeof(CodeNode) * distance(code.begin(), code.end());
}
string LZ77decode (const forward_list<CodeNode>& code)
{
string res;
res.reserve(LZ77length(code)); // can not be
for (CodeNode cn : code) {
for (size_t i = res.size()-cn.beg, e = i+cn.len; i != e; ++i)
res += res[i];
res += cn.ch;
}
return res;
}
ostream& operator<< (ostream& os, CodeNode cn) {
return os << '<' << int(cn.beg) << ',' << int(cn.len) << ',' << cn.ch << '>';
}
int main()
{
string s;
getline (cin, s);
//s = "helolohelololololololololololololo"; // для тестирования
auto code = LZ77(s,10);
for (CodeNode cn : code) cout << cn << ' ';
cout << endl;
cout << LZ77decode(code) << '\n' << s << endl;
//cout << s.size() << ' ' << LZ77size(code) << endl;
return 0;
}