#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <cstdlib>
#include <utility>

using namespace std;

struct element {
    string s;
    element *next;
};

struct list {
    element *head;
    element *tail;
    int elNum = 0;
};
struct queue {
    element *head;
    element *tail;

};

void load_data(const string &path, string &text);

void split(string &text, string &s, const string &delimEnd, char &delim);

void split(string &text, string &s, char delim = ' ');

void add_head(string arg, list *ml);

void delete_head(list *ml);

int* create_temporary_array(string pattern);

int KMP(string pattern, string target);

queue *new_queue();

void add_to_queue(string newData, queue *q);

void delete_from_queue(queue *q);

void showQueue(queue *q);


int main() {
    string text;
    load_data("inversed.txt", text);
    list *listOfSentences = new list;
    queue *que = new_queue();

    while (!text.empty()) {
        string s;
        char delim = ' ';
        split(text, s, "!?.", delim);
        list *listOfWords = new list;
        while (!s.empty()) {
            string temp;
            split(s, temp);
            add_head(temp, listOfWords);

        }

        string sentence;
        int i = listOfWords->elNum;
        while (i > 0) {
            sentence += listOfWords->head->s + +" ";
            delete_head(listOfWords);
            i--;


        }
        delete listOfWords;

        sentence.back() = delim;

        cout << sentence << endl;
        add_head(sentence, listOfSentences);
        if(sentence.find("sale")!=string::npos||sentence.find("promotion")!=string::npos||sentence.find("discount")!=string::npos||sentence.find("offer")!=string::npos){
            add_to_queue(sentence,que);
        }




    }
    cout << "_________________________" << endl;

    showQueue(que);

    cout << "_________________________" << endl;

    while(que->head!= nullptr){
        int r1 = KMP("unique offer",que->head->s);
        int r2 = KMP("mega discounts",que->head->s);
        int r3 = KMP("super promotion",que->head->s);
        int r4 = KMP("low prices",que->head->s);
        int r5 = KMP("great sale",que->head->s);
        cout << r1+r2+r3+r4+r5 << endl;
        if(r1+r2+r3+r4+r5!=0){
            cout << que->head->s << endl;
            cout << "unique offer = " << r1 << endl;
            cout << "mega discounts = " << r2 << endl;
            cout << "super promotion = " << r3 << endl;
            cout << "low prices = " <<  r4 << endl;
            cout << "great sale = " <<  r5 << endl;
        }

        delete_from_queue(que);
        cout << endl;

    }




    delete listOfSentences;
    delete que;
    return 0;
}

void load_data(const string &path, string &text) {

    ifstream file;
    file.open(path);

    getline(file, text);

    file.close();
}

void split(string &text, string &s, const string &delimEnd, char &delim) {
    size_t start = 0;
    size_t finish = text.find_first_of(delimEnd, start);
    if (text[finish] == '!' || text[finish] == ',' || text[finish] == '.') {
        delim = text[finish];
    }


    if (finish != string::npos) {
        s = text.substr(start, finish - start);
        text.erase(0, finish + 1);

    } else {
        s = text.substr(start, s.length() - 1 - start);
        text.clear();
    }
}

void split(string &text, string &s, char delim) {
    size_t start = text.find_first_not_of(delim);
    size_t finish = text.find_first_of(delim, start);

    if (finish != string::npos) {
        s = text.substr(start, finish - start);
        text.erase(0, finish + 1);


    } else {
        s = text.substr(start, s.length() - 1 - start);
        text.clear();
    }

}

void add_head(string arg, list *ml) {
    auto *el = new element;
    el->s = std::move(arg);
    el->next = nullptr;
    if (ml->head == nullptr) {
        ml->tail = el;
    } else {
        el->next = ml->head;
        ml->head = el;
        ml->elNum++;
    }
}

void delete_head(list *ml) {
    if (ml->elNum == 0) {
        cout << "lista jest pusta!" << endl;
        return;
    }
    element *temp = ml->head;
    ml->head = temp->next;
    ml->elNum--;
    delete temp;
}

int* create_temporary_array(string pattern) {
    int m = pattern.length();
    int* f = new int[m];
    f[0]=0;
    f[1]=0;
    int t = 0;
    for(int i=1;i<m;i++){
        while(t>0&&pattern[t]!=pattern[i]){
            t=f[t];
        }
        if(pattern[t]==pattern[i]){
            t++;

        }
        f[i+1]=t;
    }

    return f;
}

int KMP(string pattern, string target){
    int *f = create_temporary_array(pattern);
    int count = 0;

    int n = target.length();
    int m = pattern.length();

    int i = 0;
    int j = 0;
    while (i < n - m + 1) {
        while((pattern[j]==target[i+j])&&j<m){
            j++;

        }
        if(j==m){
            count++;
        }
        i=i+max(1,j-f[j]);

        j=f[j+1];

    }
    delete[] f;
    return count;

}

queue *new_queue() {
    queue *q = new queue;
    q->tail = nullptr;
    q->head = nullptr;
    return q;

}

void add_to_queue(string newData, queue *q) {
    element *el = new element;
    el->s = newData;
    el->next = nullptr;
    if (q->tail != nullptr) {
        q->tail->next = el;


    } else {
        q->head = el;

    }
    q->tail = el;
}

void delete_from_queue(queue *q) {
    if (q->tail != nullptr) {
        element *temp = q->head;
        q->head = temp->next;
        if (q->head == nullptr) {
            q->tail = nullptr;
        }
        delete temp;

    }else{
        cout << "Kolejka jest pusta!" << endl;
    }
}
void showQueue(queue *q){
    element *el = q->head;
    while(el->next!=nullptr){
        cout << el->s << endl;
        el = el->next;
    }
    cout << el->s << endl;
}