#include <iostream>
#include <fstream>
#include <stdio.h>
#include <string>
#include <sstream>
#include<bits/stdc++.h>

using namespace std;

FILE* file=fopen("dane.txt","r");

struct stck
{
    string word;
    stck* ptr=nullptr;
};

struct element
{
    string sentence;
    element *next=nullptr;
};

struct que
{
    element* head=nullptr;
    element* tail=nullptr;
};

string readFile();
string getMark(string &word);
void ex1ex2(que &k);
void patternPrint();
void add2Stack(stck *&top,string word);
void printStack(stck *top);
void delStack(stck *& top);
void stack2String(stck* top,string &text);
bool ex2IfSentSusp(string text);
void add2Q(que &k, string sentence2add);
void printQ(que k);
void kmp_array(string pattern, int* &t);
int findPattern(string sentence, string pattern, int* t);
void ex3(que k);
string takeOneFromQ(que &k);

int main()
{
    que k;

    cout<<"ZAD 1"<<endl<<endl;
    ex1ex2(k);
    patternPrint();

    cout<<"ZAD2"<<endl<<endl;
    printQ(k);
    patternPrint();

    cout<<"ZAD3"<<endl<<endl;
    ex3(k);


    return 0;
}

void ex3(que k)
{
    int *t;
    string sentence;
    string pattern[5];
    string temp;
    pattern[0]="unique offer";
    pattern[1]="mega discounts";
    pattern[2]="super promotion";
    pattern[3]="low prices";
    pattern[4]="great sale";
    bool ifMatch=false;
    int results[5];

    while(k.head!=nullptr)
    {
        sentence=takeOneFromQ(k);
        temp=sentence;
        transform(sentence.begin(), sentence.end(), sentence.begin(), ::tolower);

        for (int i=0; i<5; i++)
        {
            kmp_array(pattern[i],t);
            results[i]=findPattern(sentence,pattern[i],t);
            if(results[i]>0)
            {
                ifMatch=true;
            }

            delete []t;
        }
        if(ifMatch==true)
        {
            cout<<"Zdanie: "<<temp<<endl<<endl;
            for(int i=0; i<5; i++)
            {
                cout<<pattern[i]<<": "<<results[i]<<endl;
            }
        }
        ifMatch=false;
        sentence="";
        cout<<sentence<<endl;
    }
}

string readFile()
{
    string tempstr="";
    char tempChar;
    while(!feof(file))
    {
        tempChar=fgetc(file);

        if(tempChar==' ')
        {
            break;
        }

        tempstr+=tempChar;
    }
    return tempstr;
}

string getMark(string &word)
{
    char temp;
    stringstream ss;
    string char2String="";
    for(int i=0; i<word.length(); i++)
    {
        temp=word[i];

        if(temp=='?'|| temp=='!' || temp=='.')
        {
            word=word.substr(0,i);
            ss<<temp;
            ss>>char2String;
            return char2String;
        }
    }
    return "0";
}


void ex1ex2(que &k)
{
    string word="";
    string mark="";
    string text="";
    stck *ex1Stck=new stck;

    while(!feof(file))
    {
        word=readFile();
        mark=getMark(word);

        if(mark=="0")
        {
            add2Stack(ex1Stck,word);
        }
        else
        {
            add2Stack(ex1Stck,word);
            printStack(ex1Stck);
            cout<<mark<<" ";
            cout<<endl;

            stack2String(ex1Stck,text);
            delStack(ex1Stck);

            if(ex2IfSentSusp(text)==1)
            {

                if(text[text.length()-1]==' ')
                {
                    text[text.length()-1]=mark[0];
                }
                else
                {
                    text+=mark;
                }
                add2Q(k,text);
            }

            text="";
            word="";
            mark="";
            ex1Stck=new stck;
        }
    }

    stack2String(ex1Stck,text);
    printStack(ex1Stck);
    delStack(ex1Stck);
    if(ex2IfSentSusp(text)==1)
    {
        text+=mark;
        add2Q(k,text);

    }
    cout<<endl;
}

bool ex2IfSentSusp(string text)
{
    int length=text.length();

    for(int i=0; i<length; i++)
    {
        if(text[i]==':' || text[i]==',' || text[i]=='%')
        {
            text[i]=' ';
        }
    }

    int t[text.length()+2];
    int index=1;
    string tempword="";
    t[0]=1;
    for(int i=0; i<length; i++)
    {
        if(text[i]==' ')
        {
            t[index]=1;
        }
        else
        {
            t[index]=0;
        }
        index++;
    }
    t[length+1]=1;

    for(int i=0; i<length+2; i++)
    {
        if(t[i]==1)
        {
            for(int j=i+1; j<length+2; j++)
            {
                if(t[j]==1)
                {
                    tempword=text.substr(i,j-i-1);
                    transform(tempword.begin(), tempword.end(), tempword.begin(), ::tolower);

                    if(tempword=="promotion" || tempword=="discount" || tempword=="sale" || tempword=="offer")
                    {
                        return 1;
                    }
                    i=j-1;
                    break;
                }
            }
        }
        tempword="";
    }
    return 0;
}


void add2Stack(stck *&top,string word)
{
    stck *element=new stck;

    element->word=top->word;
    element->ptr=top->ptr;
    top->ptr=element;
    top->word=word;
}

void delStack(stck *& top)
{
    if(top->ptr!=nullptr)
    {
        stck *temp=top;
        top=top->ptr;
        delete temp;
    }
}

void printStack(stck* top)
{
    while(top->ptr!=nullptr)
    {
        if(top->ptr->ptr==nullptr)
        {
            cout<<top->word;
            top=top->ptr;
        }

        else
        {
            cout<<top->word<<" ";
            top=top->ptr;
        }
    }

}
void stack2String(stck* top,string &text)
{
    while(top->ptr!=nullptr)
    {
        text+=top->word+" ";
        top=top->ptr;
    }
}

void add2Q(que &k, string sentence2add)
{
    element *qEl = new element;
    qEl->sentence=sentence2add;
    qEl->next=nullptr;

    if(k.head!=nullptr)
    {
        k.tail->next=qEl;
    }
    k.tail=qEl;

    if(k.head==nullptr)
    {
        k.head=qEl;
    }
}

void printQ(que k)
{
    while(k.head!=nullptr)
    {
        cout<<k.head->sentence<<endl;
        k.head=k.head->next;
    }
}

string takeOneFromQ(que &k)
{
    string temp="";
    if(k.head!=nullptr)
    {
        temp=k.head->sentence;
        k.head=k.head->next;
    }
    return temp;
}

void patternPrint()
{
    cout<<endl<<"***************************************************"<<endl<<endl;
}

void kmp_array(string pattern, int* &t)
{
    int patternLen=pattern.length();

    t=new int[patternLen+1];
    int j=0;

    t[0]=0;
    t[1]=0;

    for(int i=1; i<=patternLen; i++)
    {
        while(j>0 && pattern[i]!=pattern[j])
        {
            j=t[j];
        }
        if(pattern[i]==pattern[j])
        {
            j++;
        }
        t[i+1]=j;
    }
}

int findPattern(string sentence, string pattern, int* t)
{
    int i=0;
    int j=0;
    int sentenceLen=sentence.length();
    int patternLen=pattern.length();
    int counter=0;

    while(i<=sentenceLen-patternLen+1)
    {
        while(pattern[j]==sentence[i+j] && j<=patternLen)
        {
            j++;
        }
        if(j==patternLen)
        {
            counter++;
        }
        i=i+max(1,j-t[j]);
        j=t[j+1];
    }
    if(counter>0)
    {
        return counter;
    }
    else
        return 0;
}