#include "ReadWriter.h"
//в ReadWriter.h все подключено (Node.h, string, vector, iostream..)
using namespace std;

pair<int, int> findMaxSubstr(string h, string p) //возвращает пару - индекс в истории и длину
{
    string trace = p + "$" + h + p;
    int n = trace.length();
    int* br = new int[n];
    br[0] = 0;
    int k = 0, iMax = -1, max = -1;
    for (int q = 1; q < n; q++)
    {
        while (k > 0 && trace[k] != trace[q])
            k = br[k - 1];
        if (trace[k] == trace[q])
            ++k;
        br[q] = k;
        int inc = q - k + 1;
        if (k > max && inc > p.length() && inc < p.length() + h.length() + 1) //наш максимальный префикс должен начинаться в истории
        {
            max = k;
            iMax = inc;
        }
        if (inc > p.length() + h.length())
            break;
    }
    delete[] br;
    /*cout << trace << endl; // слава отладочной печати!
    for (int q = 0; q < n; q++)
        cout << br[q] << " ";
    cout << "\n";*/
    if (iMax <= 0 || max <=0) //если не нашли в словаре
        return make_pair(0, 0);
    return make_pair(h.length() - iMax + p.length() + 1, max); //финт с верным индексом в истории
}
void encodeLZ77(string& s, vector<Node>& res, int histBufMax, int prevBufMax)
{
    int lenHist = histBufMax / sizeof(char);
    int lenPreview = prevBufMax / sizeof(char);

    int pointer = 0; //граница между историей и превью
    int bH = 0; //начало истории
    while (pointer + 1 < s.size())
    {
        if (pointer - bH > lenHist)
            bH += pointer - lenHist;
        pair<int, int> t = findMaxSubstr(s.substr(bH, pointer), s.substr(pointer, lenPreview));
        int shift = t.second;
        if (t.second == 0)
            res.push_back(Node(0, 0, s[pointer + shift]));
        else
            res.push_back(Node(t.first, t.second, s[pointer + shift]));
        pointer += ++shift;
    }
}

int main(int argc, const char* argv[])
{
    //Здесь предлагается задать размер окна в байтах (отдельно буфера предыстории и предпросмотра)
    //В сумме должны образовывать столько, сколько надо в задании
    //history buffer 3 kb
    int histBufMax = 1024 * 3;
    //preview buffer 1 kb
    int prevBufMax = 1024;

    ReadWriter rw;
    string s = "";
    rw.readString(s);

    //Основной структурой выбран вектор, так как заранее неизвестно какое количество элементов будет записано
    vector<Node> v;

    encodeLZ77(s, v, histBufMax, prevBufMax);

    rw.writeCode(v);
    return 0;
}